Hash Functions - Understanding Cryptography - page 296

birthday we mean any of the 365 days of the year. Our intuition might lead us to
assume that we need around 183 people (i.e., about half the number of days in a
year) for a collision to occur. However, it turns out that we need far fewer people.
The piecewise approach to solve this problem is to first compute the probability of
two people not having the same birthday, i.e., having no collision of their birthdays.
For one person, the probability of no collision is 1, which is trivial since a single
birthday cannot collide with anyone else's. For the second person, the probability
of no collision is 364 over 365, since there is only one day, the birthday of the first
person, to collide with:
P (no collision among 2 people)= 1

1
365

−

If a third person joins the party, he or she can collide with both of the people already
there, hence:
P (no collision among 3 people)= 1

1

1
365

2
365

− · −

Consequently, the probability for t people having no birthday collision is given by:
P (no collision among t people)= 1

1 1

1
365

2
365

t 1

365

−

− · − ··· −

For t = 366 people we will have a collision with probability 1 since a year has only
365 days. We return now to our initial question: how many people are needed to
have a 50% chance of two colliding birthdays? Surprisingly—following from the
equations above—it only requires 23 people to obtain a probability of about 0 . 5for
a birthday collision since:

P (at least one collision)=1 − P (no collision)

1 1

1
365

23 − 1

= 1 − − ··· −

365

= 0 . 507 ≈ 50% .

Note that for 40 people the probability is about 90%. Due to the surprising outcome
of this gedankenexperiment, it is often referred to as the birthday paradox.
Collision search for a hash function h () is exactly the same problem as finding
birthday collisions among party attendees. For a hash function there are not 365
values each element can take but 2 n , where n is the output width of h (). In fact, it
turns out that n is the crucial security parameter for hash functions. The question is
how many messages ( x 1 , x 2 ,..., x t ) does Oscar need to hash until he has a reasonable
chance that h ( x i )= h ( x j ) for some x i and x j that he picked. The probability for no
collisions among t hash values is: