How does the birthday paradox apply to random keys?

Question

I'm developing a web app where I wish to use pseudorandom keys for items, perhaps akin to Imgur. I was thinking about how many combinations I need to reduce the chance of someone guessing any random item in the database (by checking the associated URL) to x. On the performance side, it would seem to be the same (similar?) problem when I'm generating new keys randomly to avoid an excessive hit from repeated collisions.

From the birthday attack article, roughly, the number of options there needs to be (H) for a 50% chance of collision is sqrt(H). So, even if I have 10 billion (10¹⁰) possible keys, someone only needs to guess 100 thousand (10⁵) to get a collision...

Something seems severely off with my understanding of the math: if I only have a couple thousand keys used (or lets say 1) out of billions possible, it seems like the chance to randomly find it would be one in a billion.

What's relevant for me I suppose is given the number of entries I expect, and some tolerance for a possible attacker to randomly find one of said entries, how many choices do I need? Naively I'd just say it's

num_possible_key_values >= expected_entries / max_probability_to_randomly_find_one

So if I plan to accommodate in the ballpark of 10,000 entries, and want it to take a million random guesses to get lucky and find one, I should only need 10,000 * 1,000,000 keys.

Answer 1

So if I plan to accommodate in the ballpark of 10,000 entries, and want it to take a million random guesses to get lucky and find one, I should only need 10,000 * 1,000,000 keys.

Yes, this is correct. If you have $n$ (randomly chosen) valid keys out of $N$ total, then the probability of a single key being valid is $p = n/N$, and so the average number of keys one needs to test to find a single valid one is $1/p = N/n$.

Where the birthday paradox comes into play is in key generation. Specifically, if you have a total of $N$ possible keys, and you independently and randomly pick $n$ of these possible keys to be valid, then there's a risk that some of the keys you pick will be identical. In particular, the expected average number of duplicate pairs will be $(n^2-n)/(2N)$. (This is also an upper bound on the probability of there being at least one duplicate; this upper bound is a good approximation of the true probability whenever it is much less than one, i.e. when $n \ll \sqrt N$.)

What this means, in practice, is that if the number of valid keys $n$ is much less (say, less than one thousandth of) the square root of the total keyspace size $N$, then you probably don't need to worry about collisions in key generation at all, since the probability of having even a single collision is less than one in a million. Once the $n$ gets closer to $\sqrt N$, though, collisions become likely, and you will need to implement a mechanism for dealing with them.

(If you have a centralized database, dealing with collisions is pretty trivial; just pick a new random key and repeat. This is very efficient unless your keyspace is almost full (say, $n > N/2$), in which case you have bigger problems than slow key generation anyway. In some crypto schemes, however, one needs to avoid collisions without using any kind of central key database. In this case, the only possible solution is to increase the keyspace size far above the square of the highest foreseeable number of valid keys, so that having even a single collision becomes extremely unlikely.)

Answer 2

2 important points:

1. There is a difference between guessing a particular key, and guessing any one of a number of keys. The birthday example is the latter. This is one reason why a user/password pair is commonly used. You may be able to guess a password that matches someone's password, but you also have to know which user it matches in order to take advantage of it.

2. Your example of 10 billion is an extremely small number, at least in terms of normal key pool sizes. Imagine you have a random password with the requirements that it be at least 8 characters long, and you can only use capital or lowercase letters, and numbers. That's 62 different characters per digit, so the minimum pool size is 62^8 = 218 trillion possibilities. Make your minimum length 9, and now you have 14 quadrillion possibilities. Add more characters to your set and it increases to much bigger than that.

Answer 3

I don't think the birthday paradox applies here. The way the probability is computed in the birthday paradox depends only on the number of possible states (i.e number of days) and the number of attempts (i.e. number of people you look at).

But in your case the probability of a successful collision obviously not only depends on the number of attempts and number of possible states but also how much entries you have in your set. That is if you have only one entry but 100 states the probability of finding this entry will be 0.01 with one attempt and 0.02 with two attempts. If you instead have 99 entries in the set the probability with one attempt will be 0.99 and with the second attempt 1.0.

I think this problem is more like the problem of having X black and Y white balls inside the urn and you want to compute the probability that you get only white balls with N draws: in your problem you have X+Y states where X states have an entry (black ball) and Y have not (white ball). But for more details and how to compute this you might better ask at math.se or maybe crypto.se