Explain birth day attack ?

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{\textstyle {\sqrt {2^{n}}}=2^{n/2}}

  • 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 exclusiveP(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 %

Leave a reply