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

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

More precisely, collisions should be as unpredictable as hashes themselves, so the only way to find collisions is brute force.

To be fair, it is better explained later in the text. But definitely misleading.

> Also, it should be computationally infeasible to find any other word which also hashes to '...'

Yes. This is trivially obvious by reasoning that a hash is a function that maps arbitrary data to data of a fixed size. There must be collisions otherwise it couldn't hash any possible string.

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.

You're right but I'm guessing the writer is thinking of the limited list of English "words".

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

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

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.

> If you are given the value of what 'cat' hashes too but you didn't know what made it, you would never be able to find out that 'cat' was the original word.

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.

Not only that it's also false from a practical perspective because you can easily find out that 'cat' was the original word by going through a list of hashes of all English words (>rainbow table attacks). That's why you use salts.

Only now I understand why people use (sic)

> Also, it should be computationally infeasible to find any other word which also hashes to [...]

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