0

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?

  • 1
    Considering the birthday problem equivalent of your question (probability of at least two out of $n$ 8-bit numbers being the same), 20 is right about where the probability reaches 0.5. – muru Dec 17 '18 at 2:57
  • @muru Right, so the birthday attack seems to be slightly different from the classic birthday paradox scenario. My question is how? What are the steps performed where you find a collision in an avg of 16 tries instead of 20? – Nick S Dec 17 '18 at 3:42
  • I'm not familiar with the birthday attack, but it seems to be for generating a collision for a hash function. IIUC, your hash function here is the identity function? – muru Dec 17 '18 at 4:50
  • @muru Yeah, that's a good way to put it. The hash function here is f(x) = x. Or f(x) = x % 2^8, to be more precise. – Nick S Dec 17 '18 at 5:35
  • 1
    So, the article says a collision is expected by about sqrt(πH/2), and H here is 2^8, so ~ 20... Which still agrees with what you see. Are you expecting the attack to take literally 2^(N/2) tries instead of taking O(2^(N/2)) tries? – muru Dec 17 '18 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.