How often do brute force attacks find the password or key in a much shorter amount of time than the theoretical max?

Question

For a 128-bit key, it would theoretically take many years and a percentage of the entire worlds power output to check every possible key, or for 256-bit it would take 3 sexdecillion years. But the brute force attack only continues to check while it has not found the key.

What are the chances that the key is the very last key for the brute force attack to check?

What are the chances that the key is one of the first few keys to be tested by the brute force attack? or even if it's one of the keys in the first 10% of all keys to be checked by the brute force attack? Just because there are a lot of zeros on all these numbers, couldn't the brute force attacker get lucky and guess the key?

Does the huge size of the search space (for 128-bit, 3.4*10^38) reduce that possibility to an acceptable risk level? People win the lottery all the time, despite there being a 1 in 10^6ish chance.

Has this ever been tested? Has anyone ever generated hundreds/thousands/n of keys and then tried to brute force them for a short time to see how often the key is found in minutes/days?

Edit: I am now curious about the distribution of keys, is it uniform? Also, can this reasoning be extended, say I do have thousands of similar security (all 128 aes) keys to crack, when I run a brute force attack to find them, a small amount of them should be found relatively quickly right? (or quickly compared to the theoretical max 10^100... years)

Answer 1

What are the chances that the key is the very last key for the brute force attack to check?

If there are N keys, the chance is 1/N. If you have n bits of entropy, that means the chance is 2^-n.

...if it's one of the keys in the first 10% of all keys to be checked by the brute force attack?

Given that the key is random, the chance of a brute force search finding it within the first X% of tries is X%. So the chance of finding it among the first 10% is 10%. If a full search would take 10 years, the probability of the key being found within one year is 10%.

Forget about the crypto here, this is just statistics. If you have 1 000 cookies, and one is poisoned, how big is the probability that you die if you eat 10?

Does the huge size of the search space (for 128-bit, 3.4*10^38) reduce that possibility to an acceptable risk level?

Yes. If the keyspace is large enough, the risk of an attacker getting lucky is neglible. A full search of the AES-128 keyspace would take about 100 times the age of the universe. If you had spend all the time since the big bang brute forcing a key, you would still only have a 1% chance of cracking it. And if you only give yourself 100 years, the odds drop to 1 in 10¹⁰.

Has this ever been tested? Has anyone ever generated hundreds/thousands/n of keys and then tried to brute force them for a short time to see how often the key is found in minutes/days?

For small time periods, you have just a big a chance of finding a match if you try to crack one key all of the time as if you divide the time over multiple keys. So again, if you spend 100 years trying billions of keys for a little while, the chance of you getting a hit is close to zero.

Answer 2

Assuming that the key space is uniformly distributed (even if in reality it's not) you have exactly 10% chance that your key is in the 10% that will be checked first.

The thing is, even being in the 10 first % of 2^128 leave an absurdly large number of possibility. To reuse your lottery annalogy, 1 out of 10^37 is less than winning the lottery, 6 times, in a row, with the exact same ticket number.

And even assuming you are really unlucky and your key is checked in the first hour of brute forcing, the goal of someone using this method is to harvest as much user/pass data rahter than your data specificaly

Answer 3

The real question here is what is your 128 bit key based upon?

is it keygen(password)

You can usually narrow down your search significantly.

1 digit of a password can technically be 256^n where n is length.

Well if you know the password was from the US then the standard keyboard has 96 normally type able symbols. Now your down to 96^n passwords.

Further if you know where the password came from you can see there password rules.

1. Letters
2. Numbers
3. Symbols
4. 8 to 20 digits

ok #4 less than 96^7 eliminated. greater than 96^21 eliminated.

Many millions of combination can be eliminated without even testing them because they don't meet the criteria.

Now if you have lists of millions of password hashes, one of them is bound to have some version of Passw0rd$. Try the super common passwords against the whole list, and your probably going to get lucky within a few hours.