4 deleted 9 characters in body
source | link

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique.

The assumption that cryptographic hash functions are more unique is wrong, and in fact it can be shown to be often backwards in practice. In truth:

  1. Cryptographic hash functions must be designed toideally should be indistinguishable from random;
  2. But with non-cryptographic hash functions, it's desirable for them to interact favorably with likely inputs.

Which means that a non-cryptographic hash function may well have fewer collisions than a cryptographic one for "good" data set—data sets that it was designed for.

We can actually demonstrate this with the data in Ian Boyd's answer and a bit of math: the Birthday problem. The formula for the expected number of colliding pairs if you pick n integers at random from the set [1, d] is this (taken from Wikipedia):

n - d + d * ((d - 1) / d)^n

Plugging n = 216,553 and d = 2^32 we get about 5.5 expected collisions. Ian's tests mostly show results around that neighborhood, but with one dramatic exception: most of the functions got zero collisions in the consecutive numbers tests. The probability of choosing 216,553 32-bit numbers at random and getting zero collisions is about 0.43%. And that's just for one function—here we have five distinct hash function families with zero collisions!

So what we're seeing here is that the hashes that Ian tested are interacting favorably with the consecutive numbers dataset—i.e., they're dispersing minimally different inputs more widely than an ideal cryptographic hash function would. (Side note: this means that Ian's graphical assessment that FNV-1a and MurmurHash2 "look random" to him in the numbers data set can be refuted from his own data. Zero collisions on a data set of that size, for both hash functions, is strikingly nonrandom!)

This is not a surprise because this is a desirable behavior for many uses of hash functions. For example, hash table keys are often very similar; Ian's answer mentions a problem MSN once had with ZIP code hash tables. This is a use where collision avoidance on likely inputs wins over random-like behavior.

Another instructive comparison here is the contrast in the design goals between CRC and cryptographic hash functions:

  • CRC is designed to catch errors resulting from noisy communications channels, which are likely to be a small number of bit flips;
  • Crypto hashes are designed to catch modifications made by malicious attackers, who are allotted limited computational resources but arbitrarily much cleverness.

So for CRC it is again good to have fewer collisions than random in minimally different inputs. With crypto hashes, this is a no-no!

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique.

The assumption that cryptographic hash functions are more unique is wrong, and in fact it can be shown to be often backwards in practice. In truth:

  1. Cryptographic hash functions must be designed to be indistinguishable from random;
  2. But with non-cryptographic hash functions, it's desirable for them to interact favorably with likely inputs.

Which means that a non-cryptographic hash function may well have fewer collisions than a cryptographic one for "good" data set—data sets that it was designed for.

We can actually demonstrate this with the data in Ian Boyd's answer and a bit of math: the Birthday problem. The formula for the expected number of colliding pairs if you pick n integers at random from the set [1, d] is this (taken from Wikipedia):

n - d + d * ((d - 1) / d)^n

Plugging n = 216,553 and d = 2^32 we get about 5.5 expected collisions. Ian's tests mostly show results around that neighborhood, but with one dramatic exception: most of the functions got zero collisions in the consecutive numbers tests. The probability of choosing 216,553 32-bit numbers at random and getting zero collisions is about 0.43%. And that's just for one function—here we have five distinct hash function families with zero collisions!

So what we're seeing here is that the hashes that Ian tested are interacting favorably with the consecutive numbers dataset—i.e., they're dispersing minimally different inputs more widely than an ideal cryptographic hash function would. (Side note: this means that Ian's graphical assessment that FNV-1a and MurmurHash2 "look random" to him in the numbers data set can be refuted from his own data. Zero collisions on a data set of that size, for both hash functions, is strikingly nonrandom!)

This is not a surprise because this is a desirable behavior for many uses of hash functions. For example, hash table keys are often very similar; Ian's answer mentions a problem MSN once had with ZIP code hash tables. This is a use where collision avoidance on likely inputs wins over random-like behavior.

Another instructive comparison here is the contrast in the design goals between CRC and cryptographic hash functions:

  • CRC is designed to catch errors resulting from noisy communications channels, which are likely to be a small number of bit flips;
  • Crypto hashes are designed to catch modifications made by malicious attackers, who are allotted limited computational resources but arbitrarily much cleverness.

So for CRC it is again good to have fewer collisions than random in minimally different inputs. With crypto hashes, this is a no-no!

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique.

The assumption that cryptographic hash functions are more unique is wrong, and in fact it can be shown to be often backwards in practice. In truth:

  1. Cryptographic hash functions ideally should be indistinguishable from random;
  2. But with non-cryptographic hash functions, it's desirable for them to interact favorably with likely inputs.

Which means that a non-cryptographic hash function may well have fewer collisions than a cryptographic one for "good" data set—data sets that it was designed for.

We can actually demonstrate this with the data in Ian Boyd's answer and a bit of math: the Birthday problem. The formula for the expected number of colliding pairs if you pick n integers at random from the set [1, d] is this (taken from Wikipedia):

n - d + d * ((d - 1) / d)^n

Plugging n = 216,553 and d = 2^32 we get about 5.5 expected collisions. Ian's tests mostly show results around that neighborhood, but with one dramatic exception: most of the functions got zero collisions in the consecutive numbers tests. The probability of choosing 216,553 32-bit numbers at random and getting zero collisions is about 0.43%. And that's just for one function—here we have five distinct hash function families with zero collisions!

So what we're seeing here is that the hashes that Ian tested are interacting favorably with the consecutive numbers dataset—i.e., they're dispersing minimally different inputs more widely than an ideal cryptographic hash function would. (Side note: this means that Ian's graphical assessment that FNV-1a and MurmurHash2 "look random" to him in the numbers data set can be refuted from his own data. Zero collisions on a data set of that size, for both hash functions, is strikingly nonrandom!)

This is not a surprise because this is a desirable behavior for many uses of hash functions. For example, hash table keys are often very similar; Ian's answer mentions a problem MSN once had with ZIP code hash tables. This is a use where collision avoidance on likely inputs wins over random-like behavior.

Another instructive comparison here is the contrast in the design goals between CRC and cryptographic hash functions:

  • CRC is designed to catch errors resulting from noisy communications channels, which are likely to be a small number of bit flips;
  • Crypto hashes are designed to catch modifications made by malicious attackers, who are allotted limited computational resources but arbitrarily much cleverness.

So for CRC it is again good to have fewer collisions than random in minimally different inputs. With crypto hashes, this is a no-no!

3 added 42 characters in body
source | link

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique.

This is an incorrectThe assumption that cryptographic hash functions are more unique is wrong, and in fact it can be shown to be often backwards in practice. In truth:

  1. Cryptographic hash functions must be designed to be indistinguishable from random;
  2. But with non-cryptographic hash functions, it's desirable for them to interact favorably with likely inputs.

Which means that a non-cryptographic hash function may well have fewer collisions than a cryptographic one for "good" data set—data sets that it was designed for.

We can actually demonstrate this with the data in Ian Boyd's answer and a bit of math: the Birthday problem. The formula for the expected number of colliding pairs if you pick n integers at random from the set [1, d] is this (taken from Wikipedia):

n - d + d * ((d - 1) / d)^n

Plugging n = 216,553 and d = 2^32 we get about 5.5 expected collisions. Ian's tests mostly show results around that neighborhood, but with one dramatic exception: most of the functions got zero collisions in the consecutive numbers tests. The probability of choosing 216,553 32-bit numbers at random and getting zero collisions is about 0.43%. And that's just for one function—here we have five distinct hash function families with zero collisions!

So what we're seeing here is that the hashes that Ian tested are interacting favorably with the consecutive numbers dataset—i.e., they're dispersing minimally different inputs more widely than an ideal cryptographic hash function would. (Side note: this means that Ian's statementsgraphical assessment that FNV-1a and MurmurHash2 "look random" to him in the numbers data set are misguidedcan be refuted from his own data. Zero collisions on a data set of that size, for both hash functions, is strikingly nonrandom!)

This is not a surprise because this is a desirable behavior for many uses of hash functions. For example, hash table keys are often very similar; Ian's answer mentions a problem MSN once had with ZIP code hash tables. This is a use where collision avoidance on likely inputs wins over random-like behavior.

Another instructive comparison here is the contrast in the design goals between CRC and cryptographic hash functions:

  • CRC is designed to catch errors resulting from noisy communications channels, which are likely to be a small number of bit flips;
  • Crypto hashes are designed to catch modifications made by malicious attackers, who are allotted limited computational resources but arbitrarily much cleverness.

So for CRC it is again good to have fewer collisions than random in minimally different inputs. With crypto hashes, this is a no-no!

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique.

This is an incorrect assumption, and in fact it can be shown to be often backwards in practice. In truth:

  1. Cryptographic hash functions must be designed to be indistinguishable from random;
  2. But with non-cryptographic hash functions, it's desirable for them to interact favorably with likely inputs.

Which means that a non-cryptographic hash function may well have fewer collisions than a cryptographic one for "good" data set—data sets that it was designed for.

We can actually demonstrate this with the data in Ian Boyd's answer and a bit of math: the Birthday problem. The formula for the expected number of colliding pairs if you pick n integers at random from the set [1, d] is this (taken from Wikipedia):

n - d + d * ((d - 1) / d)^n

Plugging n = 216,553 and d = 2^32 we get about 5.5 expected collisions. Ian's tests mostly show results around that neighborhood, but with one dramatic exception: most of the functions got zero collisions in the consecutive numbers tests. The probability of choosing 216,553 32-bit numbers at random and getting zero collisions is about 0.43%.

So what we're seeing here is that the hashes that Ian tested are interacting favorably with the consecutive numbers dataset—i.e., they're dispersing minimally different inputs more widely than an ideal cryptographic hash function would. (Side note: this means that Ian's statements that FNV-1a and MurmurHash2 "look random" to him in the numbers data set are misguided. Zero collisions on a data set of that size is strikingly nonrandom!)

This is not a surprise because this is a desirable behavior for many uses of hash functions. For example, hash table keys are often very similar; Ian's answer mentions a problem MSN once had with ZIP code hash tables. This is a use where collision avoidance on likely inputs wins over random-like behavior.

Another instructive comparison here is the contrast in the design goals between CRC and cryptographic hash functions:

  • CRC is designed to catch errors resulting from noisy communications channels, which are likely to be a small number of bit flips;
  • Crypto hashes are designed to catch modifications made by malicious attackers, who are allotted limited computational resources but arbitrarily much cleverness.

So for CRC it is again good to have fewer collisions than random in minimally different inputs. With crypto hashes, this is a no-no!

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique.

The assumption that cryptographic hash functions are more unique is wrong, and in fact it can be shown to be often backwards in practice. In truth:

  1. Cryptographic hash functions must be designed to be indistinguishable from random;
  2. But with non-cryptographic hash functions, it's desirable for them to interact favorably with likely inputs.

Which means that a non-cryptographic hash function may well have fewer collisions than a cryptographic one for "good" data set—data sets that it was designed for.

We can actually demonstrate this with the data in Ian Boyd's answer and a bit of math: the Birthday problem. The formula for the expected number of colliding pairs if you pick n integers at random from the set [1, d] is this (taken from Wikipedia):

n - d + d * ((d - 1) / d)^n

Plugging n = 216,553 and d = 2^32 we get about 5.5 expected collisions. Ian's tests mostly show results around that neighborhood, but with one dramatic exception: most of the functions got zero collisions in the consecutive numbers tests. The probability of choosing 216,553 32-bit numbers at random and getting zero collisions is about 0.43%. And that's just for one function—here we have five distinct hash function families with zero collisions!

So what we're seeing here is that the hashes that Ian tested are interacting favorably with the consecutive numbers dataset—i.e., they're dispersing minimally different inputs more widely than an ideal cryptographic hash function would. (Side note: this means that Ian's graphical assessment that FNV-1a and MurmurHash2 "look random" to him in the numbers data set can be refuted from his own data. Zero collisions on a data set of that size, for both hash functions, is strikingly nonrandom!)

This is not a surprise because this is a desirable behavior for many uses of hash functions. For example, hash table keys are often very similar; Ian's answer mentions a problem MSN once had with ZIP code hash tables. This is a use where collision avoidance on likely inputs wins over random-like behavior.

Another instructive comparison here is the contrast in the design goals between CRC and cryptographic hash functions:

  • CRC is designed to catch errors resulting from noisy communications channels, which are likely to be a small number of bit flips;
  • Crypto hashes are designed to catch modifications made by malicious attackers, who are allotted limited computational resources but arbitrarily much cleverness.

So for CRC it is again good to have fewer collisions than random in minimally different inputs. With crypto hashes, this is a no-no!

2 added 323 characters in body
source | link

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique.

This is an incorrect assumption, and in fact it can be shown to be often backwards in practice. In truth:

  1. Cryptographic hash functions must be designed to be indistinguishable from random;
  2. But with non-cryptographic hash functions, it's desirable for them to interact favorably with likely inputs.

Which means that a non-cryptographic hash function may well have fewer collisions than a cryptographic one for "good" data set—data sets that it was designed for.

We can actually demonstrate this with the data in Ian Boyd's answer and a bit of math: the Birthday problem. The formula for the expected number of colliding pairs if you pick n integers at random from the set [1, d] is this (taken from Wikipedia):

n - d + d * ((d - 1) / d)^n

Plugging n = 216,553 and d = 2^32 we get about 5.5 expected collisions. Ian's tests mostly show results around that neighborhood, but with one dramatic exception: most of the functions got zero collisions in the consecutive numbers tests. The probability of choosing 216,553 32-bit numbers at random and getting zero collisions is about 0.43%. 

So what we're seeing here is that the hashes that Ian tested are interacting favorably with the consecutive numbers dataset—i.e., they're dispersing minimally different inputs more widely than an ideal cryptographic hash function would. This (Side note: this means that Ian's statements that FNV-1a and MurmurHash2 "look random" to him in the numbers data set are misguided. Zero collisions on a data set of that size is strikingly nonrandom!)

This is not a surprise because this is a feature wanteddesirable behavior for many commonuses of hash functions. For example, because hash table keys are often so;very similar; Ian's answer mentions a problem MSN once had with ZIP code hash tables. This is a use where collision avoidance on likely inputs wins over random-like behavior.

Another instructive comparison here is the contrast in the design goals between CRC and cryptographic hash functions:

  • CRC is designed to catch errors resulting from noisy communications channels, which are likely to be a small number of bit flips;
  • Crypto hashes are designed to catch modifications made by malicious attackers, who are allotted limited computational resources but arbitrarily much cleverness.

So for CRC it is again good to have fewer collisions than random in minimally different inputs. With crypto hashes, this is a no-no!

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique.

This is an incorrect assumption, and in fact it can be shown to be often backwards in practice. In truth:

  1. Cryptographic hash functions must be designed to be indistinguishable from random;
  2. But with non-cryptographic hash functions, it's desirable for them to interact favorably with likely inputs.

Which means that a non-cryptographic hash function may well have fewer collisions than a cryptographic one for "good" data set—data sets that it was designed for.

We can actually demonstrate this with the data in Ian Boyd's answer and a bit of math: the Birthday problem. The formula for the expected number of colliding pairs if you pick n integers at random from the set [1, d] is this (taken from Wikipedia):

n - d + d * ((d - 1) / d)^n

Plugging n = 216,553 and d = 2^32 we get about 5.5 expected collisions. Ian's tests mostly show results around that neighborhood, but with one dramatic exception: most of the functions got zero collisions in the consecutive numbers tests. The probability of choosing 216,553 32-bit numbers at random and getting zero collisions is about 0.43%.

So what we're seeing here is that the hashes that Ian tested are interacting favorably with the consecutive numbers dataset—i.e., they're dispersing minimally different inputs more widely than an ideal cryptographic hash function would. This is not a surprise because this is a feature wanted for many common hash functions, because hash table keys are often so; Ian's answer mentions a problem MSN once had with ZIP code hash tables.

Another instructive comparison here is the contrast in the design goals between CRC and cryptographic hash functions:

  • CRC is designed to catch errors resulting from noisy communications channels, which are likely to be a small number of bit flips;
  • Crypto hashes are designed to catch modifications made by malicious attackers, who are allotted limited computational resources but arbitrarily much cleverness.

So for CRC it is again good to have fewer collisions than random in minimally different inputs. With crypto hashes, this is a no-no!

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique.

This is an incorrect assumption, and in fact it can be shown to be often backwards in practice. In truth:

  1. Cryptographic hash functions must be designed to be indistinguishable from random;
  2. But with non-cryptographic hash functions, it's desirable for them to interact favorably with likely inputs.

Which means that a non-cryptographic hash function may well have fewer collisions than a cryptographic one for "good" data set—data sets that it was designed for.

We can actually demonstrate this with the data in Ian Boyd's answer and a bit of math: the Birthday problem. The formula for the expected number of colliding pairs if you pick n integers at random from the set [1, d] is this (taken from Wikipedia):

n - d + d * ((d - 1) / d)^n

Plugging n = 216,553 and d = 2^32 we get about 5.5 expected collisions. Ian's tests mostly show results around that neighborhood, but with one dramatic exception: most of the functions got zero collisions in the consecutive numbers tests. The probability of choosing 216,553 32-bit numbers at random and getting zero collisions is about 0.43%. 

So what we're seeing here is that the hashes that Ian tested are interacting favorably with the consecutive numbers dataset—i.e., they're dispersing minimally different inputs more widely than an ideal cryptographic hash function would. (Side note: this means that Ian's statements that FNV-1a and MurmurHash2 "look random" to him in the numbers data set are misguided. Zero collisions on a data set of that size is strikingly nonrandom!)

This is not a surprise because this is a desirable behavior for many uses of hash functions. For example, hash table keys are often very similar; Ian's answer mentions a problem MSN once had with ZIP code hash tables. This is a use where collision avoidance on likely inputs wins over random-like behavior.

Another instructive comparison here is the contrast in the design goals between CRC and cryptographic hash functions:

  • CRC is designed to catch errors resulting from noisy communications channels, which are likely to be a small number of bit flips;
  • Crypto hashes are designed to catch modifications made by malicious attackers, who are allotted limited computational resources but arbitrarily much cleverness.

So for CRC it is again good to have fewer collisions than random in minimally different inputs. With crypto hashes, this is a no-no!

1
source | link