Suppose I have a password made of `n` alphabetic characters. An attacker is given the hashed password and will attempt a brute force attack on cracking it.

I can envision a naive password cracker trying all combinations starting with `AAAA...A` then `AAAA...B` then `AAAA...C` etc until `ZZZZ...Z`. For this attacker, a password that starts with an `A` is going to reduce the time to crack by `25 * 26^(n-1)` (compared to starting with a `Z`).

Of course, you could first try dictionary words, variations of dictionary words, and a list of the most common passwords... but if the password was random garbage then at some point it will have to iterate over the entire character space. And if you didn't iterate over the space in some well defined way (i.e. random inputs), then you would need a mammoth amount of space to remember which inputs you already attempted (and you would have to check against at each iteration, thus slowing things down).

You could parallelize the inputs so you attempt `A...`, `B...`, `C...`, ..., `Z...` at the same time, but at some point you will run out of cores.

How do modern password crackers solve this problem?

• This question does not consider the fact that usually when trying to brute-force passwords, there are multiple targets (users). It is possible to use all these combinations, and so-on against multiple users. This means: just one of the passwords needs to be very weak, and at least one user password gets broken. Mar 9, 2014 at 19:52

They do exactly what you have suggested:

• dictionary words
• faster processors
• more processors

but they also use hash tables or rainbow tables, which allow the attacker to trade off time before getting the hashes with time taken to break afterwards. In simplistic terms they effectively pre-calculate password hashes (not exactly correct - look at our questions on rainbow tables for more info)

The problem itself is why we always recommend long passwords. Above a certain length they are effectively un-brute-forceable in the lifespan of the universe (or other appropriate milestone)

First of all, there is a huge difference between cracking single password hash and set of password hashes.

It may not be easy to crack single hash, while its trivial to crack some percent of set containing lets say 10.000 hashes.

Modern password crackers tends to crack sets of hashes, because it benefits more.