HMACs and Generic Attacks: Constructing MACs from Hash Functions
In this topic, we delve into HMACs and generic attacks on hash functions, exploring how HMACs are constructed from collision-resistant hash functions. The content discusses MACs for arbitrary length messages, the disadvantages associated with them, and how to start with a MAC for fixed-length messages to build a secure MAC. The construction process, theorem proofs, and security implications are highlighted with images for better understanding.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Birthday Attacks A WAY TO DETECT A COLLISION
Principle Of MD Strongly collision-free: Can t find any pair m1 m2 such that h(m1)=h(m2) easily (Sometimes we can settle for weakly collision-free: given m, can t find m m with h(m) = h(m ). The birthday paradox doesn t mean that there s a high probability that someone else has my birthday. Likewise, the birthday paradox doesn t mean that finding a collision with a known digest is easy. We can calculate how many messages we need to hash to have a good chance of finding a collision.
Definition 3 Birthday attacks are a class of brute-force techniques that target the cryptographic hash functions. The goal is to take a cryptographic hash function and find two different inputs that produce the same output.
The Birthday Problem 4 What is the probability that at least two of r randomly selected people have the same birthday? (Same month and day, but not necessarily the same year.)
The Birthday Paradox 5 How large must r be so that the probability is greater than 50 percent? The answer is 23 It is a paradox in the sense that a mathematical truth contradicts common intuition.
Birthday Calendar Wall 6 Equivalence to our hashing space Jan 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Feb 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Mar 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Apr 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 May 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Jun 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Jul 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Aug 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Sep 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Oct 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Nov 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Dec 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Calculating the Probability-1 7 Assumptions Nobody was born on February 29 People's birthdays are equally distributed over the other 365 days of the year
Calculating the Probability-2 8 In a room of k people q: the prob. all people have different birthdays ( ) 365 365 k 1 q =365 365 364 q =365!/(365 k)! 365k 365 363 365 362 365 p: the prob. at least two of them have the same birthdays = 5 . 0 = = 1 23 p q r
Birthday Attacks 9 Birthday paradox In a group of 23 randomly chosen people, at least two will share a birthday with probability at least 50%. If there are 30, the probability is around 70%. Finding two people with the same birthday is the same thing as finding a collision for this particular hash function.
Collision Search-1 10 For collision search, select distinct inputs xifor i=1, 2, ... , n, where n is the number of hash bits and check for a collision in the h(xi) values The prob. that no collision is found after selecting k inputs is ( ) n 1 1 1 1 2 3 1 r = n n n 1 p collision no (In the case of the birthday paradox r is the number of people randomly selected and the collision condition is the birthday of the people and n=365.)
Birthday Attacks 11 The probability that all 23 people have different birthdays is 2 1 )( 365 1 22 1 ( = 1 )...( 1 ) . 0 493 365 365 Therefore, the probability of at least two having the same birthday is 1- 0.493 = 0.507
More generally, suppose we have N objects, where N is large. There are r people, and each chooses an object. Then Exact solution: use fractions Approximate solution: 2 / 2 r N ( match a is there ) 1 P e
Birthday paradox in our class 13 What s the chances that two people in our class of 43 have the same birthday? Approximate solution: 2 2 43 r = = 1 1 . 0 92 p e e 2 365 * 2 N Where r = 43 people, and N = 365 choices
Birthday Attacks On Hash Function 14 The birthday attack can be used to find collisions for hash functions if the output of the hash function is not sufficiently large. Suppose h is an n-bit hash function. Then there are N = 2n possible outputs. We have the situation of list of length r people with N possible birthdays, so there is a good chance of having two values with the same hash value. N If the hash function outputs 128-bit values, then the lists have length around 264 1019, which is too large, both in time and in memory.
Collision Search-2 15 For large n ( ) 1 1 k 1 when x pno collision= 1 1 1 2 e ( ) e k2 2n n x n n x small is 1 1 n 1 e n ( ) n pno collision=e 1 n e 2 n e k 1 = e 1+2+3+...+ k 1 =e k k 1 ( ) ( ) n ( ) ( ) 2n
Collision Search-3 16 When r is large, the percentage difference between r and r-1 is small, and we may approximate r-1 r. r e p collision no = ( ) 2 = 1 2 2 r n r n e 2 = 2 r n 1 p e at least collision one
Birthday Attacks 17 Choosing r2/2N = ln2, we find that if r 1.177 , then the probability is 50% that at least two people choose the same object. N If there are N possibilities and we have a list of length , then there is a good chance of a match. N If we want to increase the chance of a match, we can make a list of length of a constant times . N
Collision Search-4 18 2 = = 2 r n 1 p e For the birthday case, the value of r that makes the probability closest to 1/2 is 23 2 2 r n 1 e p 1 2 =1 2 r n e p r = 2n * ln 2 2 1 r = ln( ) =1.1774 n 2 1 n p =1.1774* 365 = 22.49 1 = 2 * ln( ) r n 1 p
(Example) 19 (Example) We have 40 license plates, each ending in a 3-digit number. What is the probability that two of the license plates end in the same 3 digits? (Solution) N=1000, r=40 1. Approximation: 1 e 402 1000 = / 2 . 0 551 2. The exact answer: 1 2 39 = 1 1 ( )( 1 )...( 1 ) . 0 546 1000 1000 1000
Birthday Attacks 20 What is the probability that none of these 40 license plates ends in the same 3 digits as yours? 1 1 ( 40= ) . 0 961 1000 The reason the birthday paradox works is that we are not just looking for matches between one fixed plate and the other plates. We are looking for matches between any two plates in the set, so there are more opportunities for matches.
Birthday Attacks on Different Set/Group 21 Suppose there are N objects and there are two groups of r people. Each person from each group selects an object. What is the probability that someone from the first group choose the same object as someone from the second group? ( there a is match between tw groups o ) P 2 = / r N 1 e Eg. If we take N=365 and r=30, then ( there a is match between tw groups) o P 302 = = / 365 1 . 0 915 e
Birthday Attacks discrete logarithm 22 A birthday attack on discrete logarithm We want to solve x (mod p). Make two lists, both of length around 1st list: k (mod p) for random k. 2nd list: -h (mod p) for random h. There is a good chance that there is a match k -h (mod p), hence x=k+h. Compared with BSGS: BSGS algorithm is deterministic while the birthday attack algorithm is probabilistic. p
Attack Prevention 23 The important property is the length in bits of the message digest produced by the hash function. If the number of m bit hash , the cardinality n of the hash function is = m 2 n The 0.5 probability of collision for m bit hash, expected number of operation k before finding a collision is very close to = 2 2m k n m should be large enough so that it s not feasible to compute hash values!!!
