INVITATION TO CYBERSECURITY 176 hash generated will result in the first collision. But probabilistically, a collision will be found much sooner than this, and that is the case that needs to be used to calculate bruteforce attack resistance. This is the same idea as the math used for cracking cryptographic keys—we want to focus on the average case. Table 7.11 Using a hash function as a keystream generator for a stream cipher. A typical hash length for a modern hash function is 256 bits. 256 bits create 2256 different hash buckets. How many hashes would need to be generated to make finding a collision likely? We are looking for any two values that have the same hash. To make this exercise more accessible, we can ask the same type of question in a more familiar way: how many people need to be in a room to make it likely that any two have the same birthday? (same day and month, not year) There are 366 possible “birthday buckets” (including leap year babies), so the worst case would be 367 people. But on average, we would only need twenty-three people in order to have a better than half chance of finding a birthday collision! This number is much smaller than most people assume, and that is why this is called the birthday paradox. The reason it works is because twenty-three people yield 253 birthday comparisons: 23 x 22 / 2 = 253 Every time a person is added, his birthday gets to be compared to all the previous persons’ birthdays. So the second person’s birthday is compared with the first person’s birthday, the third person’s birthday is compared with the first and second persons’ birthdays, and so on, until the twenty-third person’s birthday is compared with all twenty-two previous persons’ birthdays. In this way, the number of comparisons grows quickly. 253 comparisons is well over half the number of possible birthdays, so it is not surprising that a collision is likely to happen after that many comparisons.
RkJQdWJsaXNoZXIy MTM4ODY=