A birthday attack 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 . The attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations (pigeonholes). With a birthday attack, it is possible to find a collision of a hash function in
- Birthday attack is a type of cryptographic attack that belongs to a class of brute force attacks – collision resistant attack.
- It exploits the mathematics behind the birthday problem or birthday paradox in probability theory.
- 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%.
birthday problem or birthday paradox concerns the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday
Birthday paradox:
- By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367
- 99.9% probability is reached with just 70 people, and
- 50% probability with 23 people.
- These conclusions are based on the assumption that each day of the year (excluding February 29) is equally probable for a birthday.
- But actual birth records show that different numbers of people are born on different days.
- The surprising result that a group of just 23 individuals is required to reach a probability of 50% that at least two individuals in the group have the same birthday, can be explained using probability theory:
Birthday paradox:
- Let P(A) is the probability that at least two people in the class have the same birthday,
- it is simpler to calculate P(A′), the probability that no two people in the class have the same birthday.
- Then, because A and A′ are the only two possibilities and are also mutually exclusive, P(A) = 1 − P(A′).
- For n= no of people in the class = 23
P(A’) = 365/365 * 364/365 * 363/365 *……… *343/365
= (365*364*363*…. 343) *(1/365 23 ) ≈ 0.492703
- Therefore, P(A) ≈ 1 − 0.492703 = 0.507297 (50.7297%).
- in general, P’(n) = 365/365 * 364/365 * 363/365 *……… *(365-n+1)/365
= (365*364*363*…. (365-n+1) ) *(1/365 n ) = 365! / ( (365-n)! * 365 n )
And P(n) = 1- P’(n) ; Evaluate for different n; when n =70, P(n) = 99.9 %