It is possible that brute force attempts are successful before the worst case, correct?

Question

When I read about a password being secure and stating that it would take X amount of week, years, etc. isn't that referring to the worst case?

What happens if the brute force method is successul in much less time than the 'worst case'?

The recent event with LastPass where they noticed a lot of traffic leaving their server had thinking about this. Could someone have downloaded my LastPass data, which has all my usernames and passwords, and attempt a brute force crack on it to decrypt it? I have used a very long password to encrypt my data which should be difficult to crack, but what about in 5-10 years when we have much faster computer hardware. Could this be cracked at that point?

Answer 1

For most cracking attacks, the average attack cost is about half the cost of the worst case. Simply put, if there are N possible passwords, you will hit the right one after about N/2. Note that this is an average: you can always "get lucky" or "get unlucky" on any single instance. This can be quantified: the probability of finding the right password after trying out M is M/N. Thus, there is a 1/10 chance of cracking the password in a 10th of the time of the worst case, 1/20 chance for the 20th of the worst case, and so on.

Answer 2

Sometimes people estimate how long it will take to crack a password based on the worst case; sometimes, based upon the average time to crack it. Usually, the average time to crack the password is half of the worst-case time.

Sure, it's possible someone could get lucky and crack the password a lot quicker than expected. Heck, no matter how strong your password is, it's possible (at least in theory) that someone could get lucky and just happen to guess your password on the first guess -- just like it's possible that you could win the lottery tomorrow. It's not very likely, though. Similarly, it's not very likely that someone will get lucky enough to crack the password a lot faster than expected.

In particular, if the worst-case time to crack the password is T tries, then there's a 1/n probability that an attacker will crack the password in T/n tries or less. For instance, if the worst-case is 1000 years, there's a 10% chance that an attacker might succeed in 100 years or less, a 1% chance that they might succeed in 10 years or less, and a 0.1% chance that they might succeed in 1 year or less.

If this worries you, the best defense is to choose a stronger password (one that will be harder to guess, so the worst-case time will be longer).

Answer 3

The time estimate for how long a brute force will take is made on several assumptions..

Depending on how the estimate is calculated, one such assumption is that the computer knows what character set your password is comprised of. If you add a single non alphanumeric symbol in your password it increases the complexity by a huge degree.

Every extra character and every character that expands the character set the brute force must go through will increase the security of your password.

When LastPass was allegedly compromised, the data garnered is likely to be in the form of a hash . These could be cracked by way of rainbow tables however they would have to be generated to a large enough set that it would include your password, this means you can pre-generate the brute force keys.

The second major flawed assumption is in the number of permutations that can be attempted per second. As an example, you could generate said rainbow tables with a vast array of machines, further you only have to generate them once and they can be re-used.