Birthday Attack In Cryptography And What You Should Know About It

Birthday attack in cryptography
Cryptographytechnique is used to secure communication by using text, numbers, etc.
The term cryptography, crypt means “hidden” and graphy means “writing”. 
Cryptographic techniques are used to hidden text. In general, cryptography contains four objectives, such as confidentiality, integrity, non-repudiation and authentication. 
Birthday attack in cryptography

Types of cryptography

Cryptography is mainly categorized into two:
• Single key or symmetric key cryptography
• Public key or asymmetric key cryptography


Cryptography attacks can be classified into two, such as:
Passive attack: The main objective of the passive attack is to obtain unauthorized access to the data. 
Active attack:Active attack contains a variation of the data in some way by conducting a similar process on the data. 

Cryptographic attacks 

Based on the methodology, the cryptography attacks are categorized as
• Ciphertext only attacks (COA) 
• Known plaintext attack (KAP) 
• Chosen plaintext attack (CPA)
• Dictionary attack 
• Brute force attack (BFA) 
• Birthday attack
• Man in the middle attack (MIM)
• Side-channel attack 
• Timing attack 
• Homograph attack

Birthday attack

Birthday attack is the one type of cryptography attack from the group of brute force attack. The birthday paradox problem was described by the higher likelihood of collisions that found among the fixed degree of permutations and random attack attempts. 
Birthday paradox problem 
For example, there are30 students and 1 teacher in a classroom. The teacher likes to finda pair of students who have a similar birth date. Soteacher raises a question for everyone to find them. 
For example, if the teacher mainly fixed the one day as November 〖30〗^th then the probability which at least one student is born on that day is 1-(364\365)^30that is about 7.9%. But, the probability is at least one student has similar data birthday as any other student. To find this out, the following equation is used 
Birthday attack in cryptography


Consider this year is a non-leap year (so 365 days) 
Assume that a person has an equal chance of being born on any day of the year
Let consider x=2
P(Two people have the same birthday)= 1-P(Two people having a different birthday)
Birthday attack in cryptography

So, for the x people probability, that is all of them have a different birth date, 
P(N People haivng differnt birthdays)
Birthday attack in cryptography

Hash function 

The hash function(H) is the transformation that provides the variable-sized input y, and it returns a fixed-size string is termed as hash value(h=H(y)). Hash functions are selected by cryptography, and it must satisfy the following requirements:
• Length of a variable is considered as the input 
• Fixed length is regarded as an output 
• H(x) is relatively easy to calculate for any given x
• H(x) is one way 
• H(x) is collision-free   
A hash function is one-way and hard to invert, where “hard to invert” means that hash value is computationally infeasible to find some input x. So, the H(x)=h. 
If the given information is x, it is computationally infeasible to find the messagey. It is not equal to x. So, the H(x)=H(y)then the H is collision-free. 

The hash of strongly collision H is also computationally infeasible to find any two data as xand y. So, H(x)=H(y). 
Let H:M=>{0,1}^n so, the hash function (|M|≫2^n)
Digital signature susceptibility 
The recent PhD research topics are mostly selected based on the birthday attacks and their paradox. The message t is typically signed by initial computing of H(m).
Here, the H-cryptographic hash function 
H(m)-secret key 
Alice wants to trick the bob into signing a fraudulent contract. Then, Alice makesa fair contract as m, and the fraudulent is represented as m^'.  Then she finds the exact position where, m changed without changing the meaning like empty lines, inserting commas/removing commas, make two spaces after/before the sentence, changing the word sense, etc. The combination of these variations she can create huge number of changes on m that are all fair contracts.

Likewise, Alice makes some of the changes tom^' that is closer to the m then H(m)=H(m^').  So she can send the fair data m to bob for the signing process. Then Alice takes the signature and attaches to their fraudulent contract. 
To avoid these kinds of attack, the hash function output should be a very long sequence of bits, so birthday attack is now computationally infeasible.

Thanks a lot for reading along. Don't forget to drop us a comment and share to your friends.
Next Post »