At 5:41 : wouldn't the worst possible case require an infinite amount of time? I could keep trying random messages, and get the same (wrong) hashes multiple times, without ever finding any message leading to the correct hash. Am I wrong?
23^2 = 529 >> 363. I think the 23 comes from this calculation : 0.50 = (364/365)^n (the probability that all n people have distinct birthdays0 which can be solved by logs. n = 253 = M(M-1)/2 easily solved algebraically .... M = 22.47 ... presumably rounded up to 23
Isnt there a possibility that the file AND the hash value is corrupt in such a way the receivers new hash value of the corrupt file matches that of the corrupt hash value? And also, isnt there also a possibility that the file made it through intact but the hash value became corrupt? Then the new hash value wouldnt match the corrupt one and the file would have to be resent for no reason.
There are two different (but related) questions here: 1. The first question is: Is it possible that errors occurring in the file and errors occurring in the hash would happen to match such that the check would pass? Assuming you are using a good hash function, that chances of both the file and the hash being corrupted consistently is almost 0. The reason for this is that even a single bit of change in the file will result in a substantial (indistinguishable from random, but on average hash of the bits) change in hash. So, let's say that the file is changed by just a single bit at random. The chances of these lining up are extremely low. Let's do some lazy math with some simplifying assumptions to get an estimate of how likely this is. Assume a 256-bit hash and an associated file. Also assume that a single bit in the file is changed, and that change results in half of the bits (128) of the hash flipping (meaning, changing from 0->1 or 1->0). How many different combinations of 128 bits out of 256 bits are there? 256 choose 128. That value is 5.767*10^75. So, out 5.767*10^75 possible ways that 128 bits in the hash could flip, only one of them is correct. That means that, assuming the bits flips are random, the changes of the hash bits being flipped to match the flipped file bit is 1/(5.767*10^75). (In reality it is even less likely, because we made a simplifying assumption that exactly 128 bits would flip.) I'm sure there are some glaring errors in my analysis, but I'm also sure that they won't matter enough to change this from "never going to happen in the entire existence of the universe". So, in short, we're safe from this happening by accident. 2. The second question is: What if the file is not corrupted, but the hash is? Won't that result in the entire file being resent? Yes, it will, and that stinks. In practice, systems that use this technique for error checking will hash and send pieces of the file instead of the whole file at once. This is done to minimize the amount of re-transmitted data.
Good presentation and personality, however, the square root of 365 is not the way to solve the birthday problem and as Saud pointed out, the square root of 365 is 19.1, not 23. You have to multiple 365/365 x 364/365 x 363/365 ... and so on until the product is
Hi Jim, This is a great point. You are right that the square root rule is not the exact solution to the birthday paradox. Instead, it is a rough rule of thumb that makes for quick and dirty math that is easy to work with in powers of two. It is close enough for the type of analysis we're doing here.
Thank you professor. It is still a good lecture in 2021. Very clear and easy to understand.
The square root of 365 is about 19
Great video
Clear, concise and lots of examples. Great lecture!
Fantastic
Great lecture! Very concise and easy to understand.
Probably the best explanation I've seen. Thanks for uploading
Thank you Dr Riley - very interesting and helpful! More please! :)
This video is GOLD
This is spectacular work, good sir.
nice lecture, great video
Excellent lecture! THANK YOU!!!
nice video nice explanation thank you very much
Very good explanation, Thanks, Subscribed.
Really good job! I'm a bit dummy and this video clear me everything!!
Awesome vid, new sub. Thanks so much, looking forward to checking out more of your videos
great video
Great video, thanks!!
very helpful , thanks, subscribed
At 5:41 : wouldn't the worst possible case require an infinite amount of time? I could keep trying random messages, and get the same (wrong) hashes multiple times, without ever finding any message leading to the correct hash. Am I wrong?
Thanks for this video! I am not quiet sure, why is it 2 to the 128. You explained, why is it 128, but I don't know, why is it 2.
2 choices (0 or 1) for each bit. 2 * 2 * 2 * 2 * 2 .... until you get to 128. aka 2^128
23^2 = 529 >> 363. I think the 23 comes from this calculation : 0.50 = (364/365)^n (the probability that all n people have distinct birthdays0 which can be solved by logs. n = 253 = M(M-1)/2 easily solved algebraically .... M = 22.47 ... presumably rounded up to 23
Isnt there a possibility that the file AND the hash value is corrupt in such a way the receivers new hash value of the corrupt file matches that of the corrupt hash value?
And also, isnt there also a possibility that the file made it through intact but the hash value became corrupt? Then the new hash value wouldnt match the corrupt one and the file would have to be resent for no reason.
There are two different (but related) questions here:
1. The first question is: Is it possible that errors occurring in the file and errors occurring in the hash would happen to match such that the check would pass? Assuming you are using a good hash function, that chances of both the file and the hash being corrupted consistently is almost 0. The reason for this is that even a single bit of change in the file will result in a substantial (indistinguishable from random, but on average hash of the bits) change in hash. So, let's say that the file is changed by just a single bit at random. The chances of these lining up are extremely low.
Let's do some lazy math with some simplifying assumptions to get an estimate of how likely this is. Assume a 256-bit hash and an associated file. Also assume that a single bit in the file is changed, and that change results in half of the bits (128) of the hash flipping (meaning, changing from 0->1 or 1->0). How many different combinations of 128 bits out of 256 bits are there? 256 choose 128. That value is 5.767*10^75. So, out 5.767*10^75 possible ways that 128 bits in the hash could flip, only one of them is correct. That means that, assuming the bits flips are random, the changes of the hash bits being flipped to match the flipped file bit is 1/(5.767*10^75). (In reality it is even less likely, because we made a simplifying assumption that exactly 128 bits would flip.) I'm sure there are some glaring errors in my analysis, but I'm also sure that they won't matter enough to change this from "never going to happen in the entire existence of the universe". So, in short, we're safe from this happening by accident.
2. The second question is: What if the file is not corrupted, but the hash is? Won't that result in the entire file being resent? Yes, it will, and that stinks. In practice, systems that use this technique for error checking will hash and send pieces of the file instead of the whole file at once. This is done to minimize the amount of re-transmitted data.
@@ryanriley5591 Thank you for your answer, very informative.
Good presentation and personality, however, the square root of 365 is not the way to solve the birthday problem and as Saud pointed out, the square root of 365 is 19.1, not 23.
You have to multiple 365/365 x 364/365 x 363/365 ... and so on until the product is
Hi Jim,
This is a great point. You are right that the square root rule is not the exact solution to the birthday paradox. Instead, it is a rough rule of thumb that makes for quick and dirty math that is easy to work with in powers of two. It is close enough for the type of analysis we're doing here.