Calculating the time required to brute force a random code

Question

Say we have amount random entry codes of length characters from an alphabet of size alphabet. The number of possible codes is then easily calculated as keyspace = alphabet ^ length.

Now take an attacker who is trying to gain entry using brute force random guessing of codes. At guess rate rate, the time in which they can all be checked (and entry is thus guaranteed) is easily calculated as keyspace / rate.

However, what I would really like to know is, how to calculate the time required for the attacker to have a given chance of finding any valid entry code. This is a system where a valid code is all you need, there is no secondary requirement like a username (think coupons). Once again, there are amount in keyspace.

E.g., how long would it take the attacker to have a 1% chance of finding a valid code? And 10%? And 25%? Etc. Or the inverse, given a specific amount of time, what are the chances?

Answer 1

For the expected case (average) the number of attempts has a linear relationship to the probability of success being considered.

expected_time = probability * keyspace / ( rate * 2)

So if the keyspace consisted of 1 billion codes and the attacker could brute force 1 million codes per second to have a 10% chance of success the attacker would need 50 seconds.

expected_time = 10% * 1000000000/(1000000 * 2)

Now in your case you state there are a multiple valid codes (amount). Can these codes be attacked in parallel? Generally we try to avoid scenarios where that is possible. This is one reason why we add salt to passwords. It prevents an attacker from attacking all possible hashed passwords in parallel. Another example would be tying a code to a given userid. Even if userid is known this limits the attacker to searching for a specific code not any valid code. If no parallel attack are possible then the above formula is true but if the attacker can perform an attack against all possible valid codes with a single attempt then the expected time is reduced by the number of valid codes (amount).

expected_time = probability * keyspace / (rate * amount * 2)

Another way to look at it is the amount of valid codes reduces the size of the keyspace (assuming attacks can be done in parallel and any valid code is acceptable). Note in neither case does the birthday problem apply so there is only a linear reduction in expected time when the attacker can perform a parallel attack. In hashing terms this would be a preimage attack not a collision attack. Still we generally try to scenarios where parallel attacks are possible because we don't want to increase the efficiency of the attack (even linearly).

Answer 2

Going back to high school probability math, the following should be close.

Given amount valid keys in a space of size space, the chance of any random guess being correct is winChance = amount / space.

Given a number of guesses (which is easily calculated from rate and time), the chance of finding 0 valid keys is (1-winChance) ^ guesses. That makes the chance of finding at least 1 valid key:

1 - ((1-winChance) ^ guesses)

What I haven't taken into account is that after each failed guess, the probability of the next guess being correct slightly increases. I'm assuming that with a large enough space / small enough amount, this increase is negligible.