Birthday attack definition
A birthday attack is an attack that occurs when someone exploits the mathematics behind the
birthday problem in probability theory to launch a cryptographic attack. The birthday problem
states that in a group of 23 people, there’s a 50% chance that at least two will have the same
birthday. This probability increases rapidly as the group size gets bigger. For instance, in a
group of 50 people, the likelihood is already over 97%.
During a birthday attack, the attacker tries to find two different input messages that produce the
same hash value, called a collision. By finding a collision, the attacker can deceive a system
into believing that two other notes are identical. For instance, they can forge a digital signature
or crack a password hash.
Birthday attacks pose a significant security threat because they are relatively easy to execute
and can undermine various cryptographic systems.
TF the Probability of at least 1 student’s birthday to fall on Oct 10th
Probability of success=1/365
Probability of failure=364/365
n=30
Probability of at least 1 student’s birthday to fall on Oct 10th is =1- [P(r=0)]
P(r=0)= 30C0 (1/365)0(364/365)30
P(r=0)= (364/365)30
Probability of at least 1 student’s birthday to fall on Oct 10th is 1-(364/365) 30
TF the probability that at least one student has the same birthday
as any other student is found using the following formula:
Assumptions –
1. Assuming a non-leap year (hence 365 days).
2. Assuming that a person has an equally likely chance of being born on any
day of the year.
Let us consider n = 2.
P(Two people have the same birthday) = 1 – P(Two people having different
birthday)
P(first person to have any day as birthday)=365/365
P(second person to have any day as birthday other than the first one’s
birthday)=364/365
P(Two people having different birthday) =(365/365)*(364/365)
P(Two people have the same birthday) = 1 – (365/365)*(364/365)
= 1 – 1*(364/365)
= 1 – 364/365
= 1/365.
So for n people, the probability that all of them have different birthdays is:
P(N people having different birthdays) = (365/365)*(365-1/365)*(365-
2/365)*….(365-n+1)/365.
= 365! /((365-n)! * 365 n)
Algorithm:
1. Choose 2n/2 random messages in M: m1, m2, …., mn/2
2. For i = 1, 2, …, 2n/2 compute ti = H(mi) => {0, 1}n
3. Look for a collision (ti = tj). If not found, go back to step 1
