The next thing I want to do is show you the general attack on collision resistant hash functions. If you remember when we talked about block cyphers. We saw a general attack on block cyphers which we called exhaustive search. And that attack forced the key size for a block cypher to be 128 bits or more. Similarly on collision resistance there is a general attack called the birthday attack which forces the output of collision resistant hash functions to be more than a certain bound. So let me show you the attack and we will see what those bounds come out to be. So here's the general attack that can work on arbitrary collision resistant hash functions. So here we have our collision resistant hash functions, supposedly, but lets suppose that it outputs N bit values. In other words, the output space is roughly of size two to the N. Now, the message space is gonna be much, much larger than N bits. Let's just say that the messages that are being hashed are say, you know, a hundred times N bits. I wanna show you an algorithm that can find the collision for this hash function H in time roughly two to the N over two. Okay, so roughly the square root of the size of the outputs space. So here's how the algorithms gonna work: what we'll do is we'll choose random two to the N over two messages in our message space that's called an M-one to M-two to the N over two. Now because the messages themselves are much bigger than N bits, they're hundred times N bits, it's very likely that all these messages are distinct. So they'll be distinct with high probability. But for each one of these messages we're gonna apply the hash function and obtain the tag T sub I. So this is of course the T sub I's are N-bit long strings. And now we're gonna look for a collision among the T sub I's. In other words, we're gonna find an I and a J such that T sub I equals to T sub J. And once we've done that we've basically found the collision because, as we said, with very high probability, M-I is not equal to M-J. But the hash of M-I is equal to the hash of M-J and therefore we found the collision on the function H. Now if it so happens that we looked through all the two to the N over two T sub I's and we don't find the collision, we go back to step one and try another set of two to the N over two messages. So the question is how well will this work, in other words how many times do we have to iterate this process until we actually find the collision? And I wanna show you that in fact the number of iterations is gonna be very, very small which means that this algorithm will find the collision in time that's roughly proportional two to the N over two. So to analyze this type of attack, I have to tell you a little bit about the birthday paradox. I imagine some of you have already heard about the birthday paradox. Here stated as a theorem, and I wanna prove it to you because everybody should see a proof of the birthday paradox at least once in their lives. So here it is, so imagine we have N random variables R-one to R-N in the interval one to B. And the only thing I'm gonna assume about them is that they're actually independent of one another. That's crucial that these N samples R-one to R-N in this interval are independent of one another. And they also happen to be distributed identically. So for example, they might all be uniform in the interval one to B, but again these would be independently uniform variables. Now it so happens that if we set N to B about the square root of B, in other words if we sample roughly the square root of B samples from the interval one to B, And to be precise, it's one point two times the square root of B. Then the probability that two of those samples will be the same is at least a half. Okay, then it turns out in fact the uniform distribution is the worst case for the birthday paradox. In other words, if the distribution from which the R-I's are sampled from is non-uniform, that in fact fewer than one point two times the square root of B samples are needed. The uniform distribution is the worst case. So we're gonna prove this for the uniform distribution and that basically also proves it for all other distributions. But the proof that I wanna show you here will hold just for the uniform distribution. Okay, so let's do the proof that's actually not difficult at all. So we're asking what is the probability that there exists an I that is not equal to J such that RI is equal to RJ. Well, let's negate that so it's basically one minus the probability that for all I not equal to J we have that RI is not equal to RJ. This basically means that no collision occurred among the N samples that we chose. Well let's try to write this out more precisely. Well we're gonna write this as one minus. And now when we choose R-one, basically it's the first one we choose so it's not gonna collide with anything. But now let's look at what happens when we choose R-two, when we choose R-two, lemme ask you, what is the probability that R-two. Does not collide with R-one. Well, R-one takes one slot so there are B minus one slots that if R-two falls into it's not gonna collide with R-one. So in other words the probability that R-two does not collide with R-one is B minus one slot divided by all B possible slots. Similarly, when we pick R-three What is the probability that R-three does not collide with either R-one or R-two? Again, R-one and R-two take up two slots. And so there are B minus two slots that remain for R-three if it falls into either one of those B minus two slots it's not gonna collide with either R-one or R-two. So I imagine you see the pattern now, so R-four it's probability of not colliding with R-one, R-two, or R-three is B minus three over B. And so on and so forth until we get to the very last R-N and the probability that R-N does not collide with the previous R-I's, well, there are N minus one slots taken up by the previous R-I's. So, if R-N falls into any of the remaining B minus N plus one slots It's not gonna collide with any of the previous R-one to R-N minus one. Now you notice that the reason I was able to multiply all these probabilities is exactly because the R-I's are all independent of one another. So it's crucial for the step That the R-I's are independent. So let me rewrite this expression a little bit. Let me write it as one minus the product of I goes to N minus one of one minus I over B. Okay. All I did is I just rewrote this as a big product as opposed to writing the terms individually. So now I'm gonna use the standard inequality that says that for any positive X, one minus X is less than E to the minus X. And that's actually easy to see because E to the minus X, if you look at it's Taylor expansion, is one minus X plus X squared over two minus and so on and so forth. And so you can see that we're basically ignoring this latter part of the Taylor expansion, which happens to be positive and as a result the left side is gonna be smaller than the right-hand side. Okay, so let's plug this inequality in, and what do we get? We get that this is greater than one minus the product of I goes from one to N minus one of E to the minus I over B okay, simply plugged in X equals I over B for each one of those terms. And the next thing about exponentials is that we multiply them, the exponents add. As a result this is simply equal to one minus E to the power of, here let me take the one over B out of the parentheses, sum of I goes from one to N minus one of I. Okay. So, all I did was I took the minus one over B out of the parentheses and we're left with simple sum of one to N minus one. And so the sum of the integers from N to N minus one is simply N times N minus one over two which it can bound by N squared over two. And so really what I get at the end here is one minus E to the power of minus N squared over two B. Okay, I literally downed it to sum here by N squared over two. Okay, very good. So now what do we do about N squared over two B? Well, we can derive exactly what N squared over two B is from the relationship here. So if you think about it, let's look at N squared over two. Well, N squared over two is 1.2 squared over two. 1.2 squared is 1.44 divided by two is .72 times the square root of B squared which is B. Okay so N squared over two is .72B, and as a result, N squared over 2B is just .72. So we get 1-E, which is a power of minus 0.72. Well so now you just plug this in to your calculator and you get 0.53, which as far as i know, is always bigger than F. So this proves the Birthday Paradox and you notice that it was crucial to a string that the samples are independent of one another, we only proved that for the uniform distribution. But as i said it is actually fairly easy to argue now that any distribution that is away from the uniform distribution will satisfy this with even a lower balance. So if you have. 1.2 squared of B, the theorem will certainly hold for none uniform distributions. The reason it is called a paradox is because it is very paradoxical that the square root function grows very slowly. In particular if you try to apply this to birth dates, so lets assume that we have a number of people in a room, and lets assume that their birth dates are independent of one another and are uniform in their interval one through 365. Then what the Birthday Paradox says is that we need roughly 1.2 times the square root of 365. Which i believe is something like 23, which says we need roughly 23 people in a room, and then with probability one half, two of them will actually have the same birth date. The reason it is called a paradox is because the number 23 seems really small to people, and yet by this theorem we just proved, with probability one half, there will be two people with the same birth date. By the way the intuition for why this fact is true is because really what the collision is counting is it is looking at all possible pairs of people. And if you have a square root of B people, then there are square root of B squared pairs. Roughly, Which is roughly B pairs total and so it's very likely that each pair collides probability one over B and if you have B pairs, it's likely that one of the pairs will collide. So hopefully this gives the intuition for where the square root comes from. Its basically from the fact that if you have N people in the room, there are N squared possible pairs. I should say by the way that even though the Birthday Paradox is often applied to birth dates, birth dates are actually not uniform at all. If you actually look at the birth dates of people, you see that there is a very clear bias towards being born in September, and for me bazaar reason there is also a biased towards being born on a Tuesday. And so when we apply the birthday paradox to birthdays, in fact the actual bound is going to be smaller than one minus two square root of B because we said that for non even form distributions you need even fewer samples before you get a collision. So let me show you how to graph the Birthday Paradox, its quite interesting how it behaves. So here set B to be a million, in other words we are picking random uniform samples in the range one to a million. And the X axis here, is the number of samples that we are picking, and the Y axis, is the probability that we get a collision among those N samples. So we see that the probability of one half happens around 1.2 square root of B. Roughly twelve hundreds, 1.2 square root of B. And you see that if we look at exactly the square root of B, the probability of a collisions is around .4 or .41. And you notice that the probability goes up to one extremely fast. For example, already at roughly two square root of B, but the probability of a collision is already 90%. Similarly, when we go bellow square root of B, the probability of a collision very, very quickly drops to zero. Okay, so there is kind of a threshold phenomena around square root of B, where the probability of a collision goes to one very quickly, above square root of B drops to zero very quickly below square root of B. So now we can analyze are attack algorithms, so let me remind you, here we chose, two to the interval two random elements in the message space, we hashed them. And so we started off with a random distribution in the message base, after we hashed them, we end up with some distribution, this distribution over tags might note be uniform, but we don't care, the point is that all these tags T1 to T2 to the N over two, are independent of one another. If we choose. Two to the N over two or 1.2 to the N over two, tags, the probability that the collision will exist is roughly one half. So let me ask you then, in that case, how many times do we have to iterate this algorithm before we actually find a collision? Well then since each iteration is going to find a collision with probability one half, we have to iterate about two times in expectation. And as a result the running time of this algorithm is basically two to the N over two evaluations of the hash function. Okay so notice also this algorithm takes a lot of space but we're gonna ignore the space issue and we're just gonna focus on the running time. Okay so this is kinda cool, this says that if your hash function outputs N-bits outputs there will always be an attack algorithm that runs in time two to the N over two. So for example if we output 128 big outputs Then a collision could be found in time two to the sixty four, which is not considered sufficiently secure. Okay, this is why collision resistant hash functions, generally are not going to output 128 bits. So let me show you some examples. The first three are actually federal standards, SHA-1, SHA-256, and SHA-512 and the fourth one is an example from the designers of AES, called Whirlpool, and so you can see SHA-1 outputs 160 bits and as a result there is a generic attack on it that runs on time two to the eighty. SHA-256 outputs 256 bits so the generic attack will run in time two to the 128 and so on and so forth. I also listed the speed of these algorithms and you notice that the bigger the block size actually the slower the algorithm is [and?] so there's a performance penalty but nevertheless there's quite a bit of benefit in terms of security. Now you notice the SHA function is actually greyed out. The SHA function although nobody has found collisions for SHA-1 yet It is still recommended that in a new project, and hopefully programing projects in this class, you don't use SHA-1, instead you use SHA-256. In particular there is actually a theoretical collision finder on SHA-1 that works in time two to the 51. So it is probably just a matter of time until someone finds a collision for SHA-1, and just kills altogether, but the current advice is that SHA-1 is still a collision resistant hash function because nobody has found collisions for it, but it is probably just a matter of time, just a few months, or few years, until a collision is found. It is a result a new product and new projects SHA-1 should not be used and only use SHA-256 or if you wanna be even more cautious then use SHA-512. So this is the end of this segment, and now we are going to turn building collision resistant hash
