Brute-force heuristics used in password cracking

Question

Existing questions on this site discuss some of the heuristics used by password cracking tools to avoid doing a completely naive brute-force search (for example, "dictionary word with number substitutions plus two characters" instead of "8 random characters").

Obviously any newly-developed tool could incorporate any heuristic the author could think of. But I'm curious... what strategies are used by common password crackers out there today?

Answer 1

As Jim says, there are two main approaches:

• Try lots of possibles from a list (dictionary/wordlist)
• Enumerate every possibility (brute force)

Each of these has tricks that can be used to improve the average time-to-crack:

For a dictionary/wordlist we can:

• use a wordlist of common passwords/phrases not just common words
• add site-/domain-specific words (e.g. "psp" if attacking the Sony list)
• add user-specific words (e.g. username/location etc. from LDAP; this could be extended to include "results from googling" and socially engineered information such as "Joshua")
• add "pass phrases" to the wordlist (e.g. phrases from the bible)
• generate variants for each word using several common "complexification" patterns (l33t, numeric pre/suffix, takining initials, etc., and combinations of patterns)
• order the wordlist (and the generated variants) based on presumed likelihood

For brute force we can:

• use target language letter frequency combinations (e.g. digraphs & trigraphs) to focus efforts on "most-likely" sequences first ("smart force")
• use a wordlist (rather than letters/digits/symbols) as the building blocks, to try to crack a passphrase

Both dictionary and brute-force can be optimised in the (scarily common) "leaked unsalted hashes" case by using a rainbow table, which contains pre-computed hashes for many millions of candidate passwords e.g. for all 8 character combinations.

Except for wordlist/passphrase brute-forcing, "phrases from the bible" and user-specific words, all of these techniques are supported in existing tools and in use. The "complexification" patterns used depend on the tool -- initial caps, numeric pre/suffix, l33t are common; digit/symbol in the middle perhaps less so but certainly supported.

User-specific wordlists are supported by tools, but not in common use against web accounts, AFAIK, where getting low-hanging fruit gives the best return. Custom wordlists -- from the bible or anywhere else -- could also be provided. Such techniques are more likely to be used when there is a specific target.

Answer 2

As has been already mentioned there's really only two main ways of approaching the problem (brute-force and dictionary based) (assuming that the password are not protected by a flawed algorithm or implementation). From what I've seen the main add-on to those strategies is to try and add a probability element to the cracking, so if we know that the password '123456' is a very common one for similar password lists to the one we're looking at we start with that.

There was an interesting presentation at Defcon a couple of years back on this (link here) which covered some of this around probabalistic cracking and word mangling strategies for dictionary attacks. There's also some good onward links in the presentation.

There's also a good collection of wordlists from cracked password database on the skull security site here some of which are already listed by probability.

Answer 3

Take a look at Supercharged John the Ripper Techniques. It goes quite in-depth explaining about password cracking methods and techniques (how to use password cracking software efficiently).

I think it gives a good point of view about the whole "password cracking operation". Also, it talks about how to create passwords "that aren’t based on known patterns".

Answer 4

The two big ones are dictionary and brute force. As you know brute force is pretty inefficient when the number of character becomes large. Sure people could develop a statistical analysis for password cracking, but the truth of the matter is that no one really cares. Most passwords are not harvested from cracking passwords, they are socially engineered out. Those that are not social engineered are cracked from either vulnerability in code, or taking from a database that probably didn't salt the hashes.

For example in the news these days people are dumping password files in the MB range, none of those passwords were brute forced or cracked.

Now if we look at common password cracking tools out there, for example John the Ripper (my personal favorite), you see that it doesn't really employ any 'smart' techniques. You can brute force, you can use a dictionary (or other word list), or you can use top common passwords.

In the future I could see password crackers becoming personalized (like medicine), you don't want to have a huge word list of passwords a target would never think of, you want to target that person and you know things about this person. You could give your tool the name of a social networking site and have it mine data, abstracting passwords. Or you can give it other personal information.

One thing to note is, it is always easier to attack the person than the machine (generally). Thats my two cents on this.