Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 02-39 Strong Collision Resistance

Get Embed Code
1 Language

Showing Revision 1 created 04/27/2012 by Amara Bot.

  1. [Evans] The key point is that this was for weak collision resistance.
  2. For weak collision resistance, our assumption,
  3. an attacker needs to do about 2 to the b work where b is the number of hash bits
  4. to have a good chance of finding a collision.
  5. Strong collision resistance is harder than weak.
  6. To obtain strong collision resistance is actually much harder,
  7. and we'll see that we need about twice as many bits for that--
  8. that the attacker's effort is more like 2 to the b over 2,
  9. so we'll need about twice as many output bits in our hash function to provide this.
  10. The reason for this is because of what's known as the birthday paradox.
  11. It's called a paradox. It's not really a paradox.
  12. It's a surprise to people who don't follow the mathematics on this,
  13. but there's nothing paradoxical about it.
  14. It's not like the Berry paradox that leads to a contradiction.
  15. The way this is usually framed is you have some group of k people--
  16. let's say it's a kindergarten classroom--
  17. and you want to know what the probability that 2 people have the same birthday.
  18. The reason this is called a paradox is the answer is actually much higher
  19. than most people expect. So let's compute this.
  20. We'll assume that there are no leap years and that birthdays are uniformly distributed.
  21. We assume the same property for our outputs of our ideal hash function.
  22. So we'll compute the complement probability that there are no duplicates,
  23. and then the probability that there is at least 1 duplicate is 1 minus this.
  24. And the way to think about that is we can go through the people in the class.
  25. We can assign some birthday to each one.
  26. So we'll assign b0 to the first one, b1 to the second one,
  27. keep assigning birthdays.
  28. There are lots of different ways we could do that.
  29. In order to assign birthdays with no duplicates,
  30. then there's a limited number of ways that we can pick any of 365 days
  31. for the first birthday.
  32. For the second one, if we want no duplicates,
  33. we can't use whatever day we pick for the first one.
  34. So it will be that times 364 times 363 and so forth,
  35. and that's the number of ways to assign birthdays with no duplication.
  36. We're trying to compute the probability, so we're going to divide that
  37. by the number of ways to assign with duplication,
  38. which is just 365 choices for each person.
  39. So in general, this first value is n factorial divided by n minus k factorial,
  40. and the bottom result is just n to the k.
  41. N is the number of possible days or the number of possible hash outputs.
  42. K is the number of trials.
  43. And so our probability that there are duplicates is just 1 minus this.
  44. This is what we need for strong collision resistance.
  45. It's higher than what we needed for weak collision resistance,
  46. which was 1 minus 1 minus 1 over n to the k.
  47. So to actually compute this, these numbers would get really big
  48. if we tried to actually compute the factorials.
  49. Instead we need to use approximations to do this.
  50. But to give you some idea what the results are like,
  51. if we have the duplicate birthday question where we have 365 days and 20 people,
  52. the probability that there's at least 1 duplicate exceeds 0.4.
  53. If we're thinking about hash collisions, if we only had a 64-bit hash
  54. and our attacker was much weaker than the one we hypothesized--
  55. let's say they can only do 2 to the 32--that's already almost a 40% chance of success.
  56. This success goes up quite quickly.
  57. If the attacker can do 2 to the 34 hashes, then the success probability is very close to 1.
  58. So the conclusion is that given an ideal hash function
  59. with N possible outputs, an attacker needs about N guesses to find an input
  60. that hashes to a particular value but only needs about the square root of N guesses
  61. to find a pair that collide.
  62. This assumes the attacker can store all those hash values as they try the guesses
  63. and compare it to all the previous ones.
  64. This is the reason why hash functions need to have large outputs.
  65. SHA-1, which was a widely used hash function, used 160 bits in its output.
  66. This was actually broken.
  67. There is a way to find collisions using SHA-1 with only 2 to the 51 operations--
  68. much fewer than the 2 to the 80 that one would expect from this square root estimate,
  69. and that's because of mathematical weaknesses in the way SHA-1 works.
  70. SHA-2, the output can be either 256 or 512 bits.
  71. As long as there aren't mathematical weaknesses in the cipher,
  72. if it was a really ideal hash function, this would be big enough to defeat any realistic attacker,
  73. but there are beginning to be suggestions that there may be ways to break this.
  74. No practical breaks have been found yet.
  75. And SHA-3, the winner is expected to be announced later this year.
  76. So for the rest of this class we're going to assume that we do have an ideal hash function
  77. and that it has enough outputs to provide strong collision resistance
  78. against a motivated attacker.