Re:How Hash Algorithms Work (2007)
by winston1984 on Friday January 13, 2017 @08:28AM
(#13390594)
>They do.
>All hash functions have collisions.
This is wrong. There is something called a perfect hash function:
https://en.wikipedia.org/wiki/Perfect_hash_function
>a perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions. In mathematical terms, it is a total injective function.
They are very handy for hash tables with constant worst-case lookup time.
While very useful, you can only construct a collision-free hash function if you know all possible inputs. Otherwise perfect hash functions can only give guarantees over the frequency of collisions.
In the more general case, for a hash function with n bits output, the pigeon hole principle demands that we have a collision at least every 2^n inputs.
Though 2^n could be much larger than the number of items in the observable universe fairly quickly.
Re:How Hash Algorithms Work (2007)
by blauditore on Friday January 13, 2017 @07:13AM
(#13390208)
More precisely, collisions should be as unpredictable as hashes themselves, so the only way to find collisions is brute force.
They do. The text is somewhat misleading and not properly explaining that.
All hash functions have collisions. But from a cryptographically secure hash function we expect that nobody is able to find such a collision. They exist, but the computational power to find one is not available to humans.