4

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?

migrated from crypto.stackexchange.com Mar 10 '14 at 18:12

This question came from our site for software developers, mathematicians and others interested in cryptography.

  • 1
    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. – user4982 Mar 9 '14 at 19:52
3

The final part of your question is easy to answer:

They do exactly what you have suggested:

  • dictionary words
  • common passwords
  • 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)

1

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.

Anyway, if you ask about methods, your intuition is right.

Whole story starts from dictionary attacks. Ofcourse dictionary is not set of words only. Good dictionary contains also patterns. For example qazxswedcvfrtgb seems quite strong, but if you look at your keyboard, you may notice its obvious pattern.

In real world, where crackers cracks sets of hashes, story ends here. Few-million-word dictionary will allow you to crack from 5% to 50% hashes in set.

Anyway, if set is quite small or you gonna crack single password, that is the point where brute force shows up.

You have mentioned parallelization. Nowadays parallelized becomes rather distributed. If you have some botnet, you can install there MPI or PVM and perform distributed computations. It's really awesome, because its scalability.

0

Real crackers will try the more commonly used passwords first. They will first use names, dictionary words, lists of known used passwords, and variations on all of these. Here is a description of one such effort on a list of hashes that was published:

http://www.thetechherald.com/articles/Report-Analysis-of-the-Stratfor-Password-List

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.