To understand the constraints or potential weaknesses of hash functions,
there are two concepts we need to discuss.
The first is the pigeonhole principle and the second is the birthday paradox.
First, let's take a look at the pigeonhole principle.
Imagine we have nine pigeonholes,
if we have nine pigeons then one pigeon can be placed in each hole.
That is suppose we have n number of pigeons and m number of holes.
If n equaled m that means there's exactly one pigeon per hole.
Now if we add another pigeon then there will be one hole with two pigeons.
That is if n, the number of pigeons is greater than m the number of holes
then there's at least one hole that must have more than one pigeon.
Now let's apply the pigeon hole principle to another problem.
How many people do we need to have in a room
such that there's a good chance that two of them will have the same birthday.
There are 365 birthdays and we can think of these birthdays as the pigeon holes.
How do we calculate the probability that two people in the room
have the same birthday.
Obviously, if you want the probability to be 100%,
we need 366 people and that's the pigeonhole principle.
Because we have 365 birthdays or 365 pigeonholes.
So we need 366 pigeons, or
people, in order to make sure that two of them will have the same birthday.
Now suppose, we only need a good chance,
say only 50% chance, that two people in the room would have the same birthday.
How do we calculate how many people do we need in a room?
We can solve this problem using the following procedure.
We can model this problem of having n people
choosing from k days as their birthdays.
Of course k is 365.
If we allow everybody to choose any of the k days then
there are k to the n that many scenarios.
Because for each of the n people, they can choose any of the k days.
So there are k to the n, that many possible scenarios.
On the other hand,
if we insist that no two people should have the same birthday,
then the number of scenarios is choosing n out of k without replacement.
And that is k(k-1) times k- 2, so on and so forth, and (k- n +1).
Because for the first person, he can choose any of the k days.
And once he makes his choice, then the next person can only have k- 1 choices.
Because we don't want the second person to have the same birthday as the first
person.
And once the first two people have chosen their birthdays,
then a third person can only have k-2 choices.
And so and so forth.
So this is the number of possible scenarios when we insist that
no two people should have the same birthday.
Then we can use this formula to compute a probability where
there's a scenario where two people share the same birthday.
And this can be approximated to n(n-1)/2k.
Therefore if you want this probability to be 0.5 meaning that
there's 50% chance that two people would share the same birthday
then n should be the square root of k.
Again this is just an approximation.
If k=365 then its square root of k=19.
That means as an approximation if we have 19 people in a room,
there is a good chance that two of them share the same birthday.
I've tried this in my class every year with the students in my classroom.
And it always works out as the math tells us.
Once we understand the pigeonhole principle and
birthday paradox, we may realize that some of the properties of hash function
seem to contradict each other.
In particular, a hash function can take as input data of any size and
the output is always a fixed size.
Since the size of hash value is fixed,
that means that there are fixed number of possible hash values.
On the other hand since the input to hash functions
can be of any size that would mean that
there are many many more possible inputs to the number of possible outputs.
In other words, there are many more pigeons than the pigeonholes.
Then applying the pigeonhole principle,
many inputs were mapped to the same output hash value.
In other words, many different input messages will have the same hash value,
but this violates the property of collision resistance.
However, if we take a closer look at hash function properties, in particular,
the collision system properties.
They only say that it should be compositionally in feasible
to find two different messages that have the same hash value.
It did not say that it should be mathematically impossible
to find such collision.
In other words, although it is mathematically possible
to find the collision, the hash function property says that
we want to make it invisible, or impractical, to find such collision.
So how do we accomplish this?
Obviously, the larger the number of possible output hash values,
the harder it is to find the collision.
In other words, the longer the length of the output hash value, the better.
In short, to avoid collision, we should use longer hash values