>The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing.
Don't hashing functions have collisions?
Don't hashing functions have collisions?
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.
> Also, it should be computationally infeasible to find any other word which also hashes to '...'
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.
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.
Usually you want a hash that maps similar strings to completely different output hashes (and I guess that's what the author actually wanted to describe). But that is not a necessity of a hash function, just a usual property.
1.46 x 10^48 = sha1 possible outputs
~7.5 x 10^5 = total English words [1]
If you computed all ~750,000 hashes for all known English words, none of the sha1 hashes will match sha1("cat"). I'm guessing that you still wouldn't get a collision if you include all words from all world languages.
For "words" to generate a collision, you'd have to increase the input domain by allowing "words" to mean any sequence of bytes (e.g. bytes of jpg image or audio file).
[1] https://en.oxforddictionaries.com/explore/how-many-words-are...
That is way overkill - the input domain could just be strings of words. Each word of a typical English text adds about one byte of entropy (2^8 states). We get a probable collision by having a number of text states around the square root of the number of hash states (because of the birthday paradox). So, sqrt(10^48) = 10^24 = (10^3)^8 which is about (2^10)^8. So the space of ordinary 10-word strings is big enough to give a sha-1 collision, without invoking inputs like binary files.
This is false or inaccurate at best too. More correct would be that it should be computationally infeasible for any one entity to have any reasonable chance to obtaining the inverse of a hash, in the foreseeable future.
With all hashing functions in existence, it's always theoretically possible to find the inverse, and that should be pointed out.
He knows there are collisions, he just chose to start with the simplest explanation and add the useful details as he moves on. It's fine by me, even though engineers tend not to like that (they prefer accuracy from the word go).