What is Birthday Attack
§A birthday attack is a name used to
refer to a class of brute-force attacks. It is a type of cryptographic attack
that exploits the mathematics behind the birthday problem in probability
theory. This attack can be used to abuse communication between two or more
parties.
§It gets its name from the
surprising result that the probability that two or more people in a group of 23
people share the same birthday is greater than 50.7%. Such a result is called a
birthday paradox.
§Birthday attacks are often used to
find collisions of hash functions. However to understand birthday attack we
have study the birthday problem.
Birthday Problem
§In probability theory, the birthday problem
or birthday paradox concerns
the probability that, in a set of
randomly chosen people, some pair of them will have the same birthday.
§By the pigeonhole principle, the
probability reaches 100% when the number of people reaches 367, since there are
366 possible birthdays, including February 29.
§However, 99.9% probability is
reached with just 70 people, and 50% probability with 23 people. These
conclusions include the assumption that each day of the year (except February
29) is equally probable for a birthday.
§The mathematics behind this problem
led to a well-known cryptographic attack called the birthday attack, which uses
this probabilistic model to reduce the complexity of finding a collision for a
hash function.
Mathematical base of Birthday Problem
§The problem is to compute the
approximate probability that in a group of n
people, at least two have the same birthday.
§The goal is to compute P(A),
the probability that at least two people in the room have the same birthday.
§However, it is simpler to calculate
P(A'),
the probability that no two people in the room have the same birthday. Because A
and A'
are the only two possibilities and are also mutually exclusive, P(A) = 1 − P(A').
§When events are independent of each
other, the probability of all of the events occurring is equal to a product of
the probabilities of each of the events occurring. Therefore, if P(A')
can be described as 23 independent events, P(A')
could be calculated as P(1) × P(2) × P(3) × ... × P(23).
§
§The 23 independent events
correspond to the 23 people, and can be defined in order. Each event can be
defined as the corresponding person not sharing his/her birthday with any of
the previously analyzed people.
§For Event
1, there are no previously analyzed
people. Therefore, the probability, P(1),
that Person 1
does not share his/her birthday with previously analyzed people is 1, or 100%.
§Ignoring leap years for this
analysis, the probability of person 1 can also be written as 365/365, for
reasons that will become clear below.
§For Event
2, the only previously analyzed people are
Person 1.
Assuming that birthdays are equally likely to happen on each of the 365 days of
the year, the probability, P(2),
that Person 2
has a different birthday than Person
1 is 364/365. This is because, if Person 2
was born on any of the other 364 days of the year, Persons 1
and 2
will not share the same birthday.
§Similarly, if Person 3
is born on any of the 363 days of the year other than the birthdays of Persons 1
and 2,
Person 3
will not share their birthday. This makes the probability P(3) = 363/365
§P(A')
is equal to the product of these individual probabilities:
§Finally P(A’)
= 0.492703
§Now as
P(A)=1-P(A’)
then P(A)= 1- 0.492703= 0.507297 or 50.7%
§So the possibility of 2 person in a
group of 23 people have same birthday is 50.7%
No comments:
Post a Comment