I thought I understood the birthday attack until I tried to actually implement it. Either I'm implementing it wrong, or there's something wrong with my interpretation of the resulting probabilities. Because when I simulate it, it takes greater than 2^(N/2) tries.
I simplified it to the problem of choosing random numbers until I choose one I've already chosen before. Already there may be problems, as the time complexity may not be equivalent to a realistic birthday attack. But if it's wrong, I expect it's on the conservative side, since this should be the easiest way to find a collision.
Here is my full code (Python 3). It tries to find a collision between two random 8-bit numbers. It repeats this 100,000 times, and reports the average and median number of tries.
import random def birthday_attack(choices): tries = 0 max_tries = choices**2 chosen = set() choice = None while choice not in chosen and tries < max_tries: tries += 1 if choice is not None: chosen.add(choice) choice = random.randrange(choices) return tries trials = 100000 tries = [birthday_attack(2**8) for i in range(trials)] print(sum(tries)/trials) tries.sort() print(tries[trials//2])
The result is consistently an average of about 20.7 tries. But it should take 16, as 2^(8/2) = 2^4 = 16!
What am I missing here, and how would a proper 2^(N/2) birthday attack be performed?