How does the birthday paradox apply to random keys? 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 (1010) possible keys, someone only needs to guess 100 thousand (105) 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.
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 &gt; 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.)