10 ms·

>>FNV-1a collisions >>altarage collides with zinke >>altarages collides with zinkes I found this most interesting. I have no idea how FNV-1a is constructed b

by ultimoo 13y ago

>>FNV-1a collisions >>altarage collides with zinke >>altarages collides with zinkes I found this most interesting. I have no idea how FNV-1a is constructed but I'm sure this is an interesting (mathematical?) quirk in an otherwise great algorithm since it had only 4 collisions for more than a couple of hundred thousand inputs.

Brandon0 13y ago
I saw that too. DJB2a also has >>playwright collides with snush >>playwrighting collides with snushing
netdog 13y ago
It's not surprising, and it is not peculiar to FNV-1a. Most of these hashes will exhibit this same behavior. Since the hash iterates over the characters in the string, once you find two colliding strings S and T, if you append any other string to both S and T, the hashes of S' and T' will also be identical. Try it yourself: #include <stdio.h> #include "hash_32a.c" int main(int argc, char* argv[]) { const char* s[] = { "altarage", "zinke", "altarage_foo", "zinke_foo", "altarage_xyzzy", "zinke_xyzzy" }; int i; for (i = 0; i < sizeof s / sizeof (char*); ++i) { Fnv32_t x = fnv_32a_str(s[i], FNV1_32A_INIT); printf("%s: %08x\n", s[i], x); } } $ ./test_fnv1a altarage: e460d8b6 zinke: e460d8b6 altarage_foo: 3d8619c5 zinke_foo: 3d8619c5 altarage_xyzzy: 2a6373cf zinke_xyzzy: 2a6373cf
joshdick 13y ago
Yeah, that seems to violate the goal of the avalanche effect. http://en.wikipedia.org/wiki/Avalanche_effect http://en.wikipedia.org/wiki/Avalanche_effect
- dreish 13y ago
  That's a design goal for cryptographic hash functions, which these are not.
  - dllthomas 13y ago
    For something like English words, where you will have a lot of common prefixes and suffixes, it seems a legitimate design goal as well (though it may not be a tradeoff worth making, to be sure).

by ultimoo 13y ago

Brandon0 13y ago

I saw that too. DJB2a also has >>playwright collides with snush >>playwrighting collides with snushing

netdog 13y ago

It's not surprising, and it is not peculiar to FNV-1a. Most of these hashes will exhibit this same behavior. Since the hash iterates over the characters in the string, once you find two colliding strings S and T, if you append any other string to both S and T, the hashes of S' and T' will also be identical. Try it yourself: #include <stdio.h> #include "hash_32a.c" int main(int argc, char* argv[]) { const char* s[] = { "altarage", "zinke", "altarage_foo", "zinke_foo", "altarage_xyzzy", "zinke_xyzzy" }; int i; for (i = 0; i < sizeof s / sizeof (char*); ++i) { Fnv32_t x = fnv_32a_str(s[i], FNV1_32A_INIT); printf("%s: %08x\n", s[i], x); } } $ ./test_fnv1a altarage: e460d8b6 zinke: e460d8b6 altarage_foo: 3d8619c5 zinke_foo: 3d8619c5 altarage_xyzzy: 2a6373cf zinke_xyzzy: 2a6373cf

joshdick 13y ago

Yeah, that seems to violate the goal of the avalanche effect. http://en.wikipedia.org/wiki/Avalanche_effect http://en.wikipedia.org/wiki/Avalanche_effect

dreish 13y ago
That's a design goal for cryptographic hash functions, which these are not.
- dllthomas 13y ago
  For something like English words, where you will have a lot of common prefixes and suffixes, it seems a legitimate design goal as well (though it may not be a tradeoff worth making, to be sure).