How short can a shortened base 62 url path be and be reasonably protected from a brute force attack?

Question

If one is creating pseudo-random base 62 url paths, and one didn't want those paths to be reasonably vulnerable to brute force attack. How short could they be?

Reasoning

Now one could have expiring short urls and urls expecting to be read from a particular device key, and many other measures. Also I'm sure there are ways to sniff out a url as it routes its way around the internet. But I just want to set that aside to simplify the question towards what the minimum length of a url can be without it being fairly vulnerable to a brute force attack.

Of course, any url could be guessed at random, but if there are enough characters in a secret code then guessing that code can become almost impossible. For example, password length requirements often force users to pick longer passwords so that they can be hardened to certain brute force and/or guessing attacks. Most web servers or arrays of web servers can only respond so quickly to secret key requests, so there is generally an upper bound on how many attempts can be tried per second.

With a base 62 url path code, if my vague memory of math serves me, there are 62 to the N power possible path codes, where N is the length of the url path code. 4 characters is too short because that would only provide about 14 million codes, some popular web sites and applications have more users than that such that you wouldn't even be able to provide enough shortened urls. 6 characters seems popular among quickly expiring codes, but even that is pushing it if one had a lot of usages. On the other hand, a 100 character length code is probably unnecessarily large. A code that large seems both impossible to guess at random and difficult to brute force while providing more usages than most humans living on earth could find for a code of that length.

So that leads me to wonder where is a nice middle ground between 6 characters and 100 character length codes? What is a good minimum length for a base 62 url code? 16 characters?

Answer 1

Only YOU can stop brute force attacks!

But, seriously - we must model what it is that we have, and what we want to achieve.

Let us start with how many "real" URLs we need. Let this number be N.

Now assume there is some level of protection (possibly none; actually, bandwidth and computing power to receive the request and reply with a 404 Error always provides a practical, if possibly very high, limit) against brute force attacks, that limits them to M attempts per second.

Finally let us assume that by "stopping brute force" we mean we want the URL to remain secret for an average time of T seconds.

When brute forcing an item from a space of cardinality K, the first attempt has a probability of (K-1)/K of failing (all values but one of the K available are incorrect). The second has a probability of (K-2)/(K-1), because the space to be explored is now diminished to K-1, and all these values but one are still incorrect. The probability of failing both attempts is the product of the two probabilities, so ((K-1)/K)*((K-2)/(K-1)), which is (K-2)/K. In the end, the probability of failing all of the first H attempts is (K-H)/K.

If we want, say, a 99% probability of the URL to remain undisclosed for T seconds (which equates to M*T attempts), it must be that the unknown number of possible values K is such, that (K-MT)/K = 99%, or (K-MT) = 0.99*K, which means M*T = 0.01*K; or K = 100*MT (for a generic safety probability of P%, it is K = MT*100/(100-P) ).

This gives us K for any given M, T and P.

We need this K to hold for all our N codes, so the actual width of the data space must be MNT/(100-P).

If we can limit the attempts to 10 per second, and want one year's leeway (about 32 million seconds) with a safety of 99% for our 10 million codes, 10*1E7*3.2E7*100 = 3.2E17. Since log10 of 62 is about 1.7924, CEIL(18/1.7924) = 11 should be a reasonable figure.

In the end, the number we seek is CEIL(LOG10(MNT/(100-P))/LOG10(62)).