This blog entry is of the form of some working notes to help me get to grips with this area of security. Would welcome corrections!
There are two basic forms of password cracking :-
- Brute force cracking where every possible password combination is tried.
- Dictionary cracking where the password cracker uses a list of possible passwords to try … and optionally some algorithms for varying each word in the dictionary.
I’m more interested in brute force cracking for now, so I’ll just say a few words about dictionary cracking …
Password Hashes
Some people are under the mistaken impression that it is possible to protect against password cracking by preventing multiple login attempts – try to login more than 5 times in a minute, and the account is locked.
People trying to break into systems know about this of course, so they rarely if ever try it (the exception is multiple attempts against equipment that does not perform account lockouts). What they do is obtain the encrypted password in some way – grabbing the /etc/shadow file from a Unix system, dumping Windows password hashes, etc.
Once you have a password hash, or a number of password hashes, it is possible to attempt to crack the passwords. Not by trying to reverse the password encryption – that should be impossible, but by using the same algorithm for encrypting the password in the first place.
For instance if someone sets their password to “bad”, the password hash that gets stored in ActiveDirectory or in a Unix system’s /etc/shadow file may look something like “bae60998ffe4923b131e3d6e4c19993e” (actually it won’t but we’ll gloss over that detail for now). The password cracker starts encoding 1 character passwords, moving onto all possible 2 character passwords, 3, etc.
Eventually he or she finds one that matches that “hash” at which point they will have the account’s password.
Dictionary Cracking
Brute force password cracking has historically been thought of as too computationally intensive to try, so people resorted to restricting the amount of passwords to search through by observing that most people use either simple words, or words made slightly more obscure through some method.
For example, the following are some passwords picked from a list of frequently found passwords (but before getting smug about your password being nowhere near as this simple, you may want to check first) :-
- password
- letmein
- xxxxxxxx
- qwerty
- 123456
In addition, people often take a simple word like “monday” and make it more complex by replacing certain letters with digits – l33t speak – so “monday” becomes “m0nday”. There is no point to this at all – it is one of the most common algorithms for supplementing a dictionary. Similarly adding digits to the end of a word, etc.
Brute Force Cracking
The option of brute force cracking is the process of going through every single password combination and trying each one in turn. This would seem to be a very slow process, but computers are becoming quicker and quicker. For example, with a GPU password cracker, my workstation can tackle around 380 million passwords a second … and it is not an especially quick GPU!
As to how fast password cracking could be today, it is hard to say … some of the more interesting hardware out there doesn’t come with benchmarks, and there’s some guesswork involved. But it is probably safe to say that nothing quite comes up to the 100 billion password attempts a second mark … yet.
It is relatively easy to calculate the number of possible passwords for any particular length … take the size of the character set used in the password, which can usually be assumed to be 96 (all ASCII without the control set) and raise to the power of the length of the password.
| Length |
Passwords |
Time (380M/s) |
Time (100 billion/s) |
| 2 |
9216 |
<1s |
<1s |
| 3 |
884736 |
<1s |
<1s |
| 4 |
84934656 |
0.2s |
<1s |
| 5 |
8153726976 |
23s |
<1s |
| 6 |
782757789696 |
37m |
8s |
| 7 |
7.5E13 |
59h |
12m |
| 8 |
7.2E15 |
5725h |
20h |
| 9 |
6.9E17 |
62 years |
1916h |
| 10 |
6.6E19 |
6035 years |
20 years |
| 11 |
6.4E21 |
577,845 years |
2028 years |
| 12 |
6.1E23 |
55473145 years |
193297 years |
There are several points to learn from this table :-
- The numbers of passwords gets very large very quickly. But not quickly enough to keep up with password crackers.
- Any password of less than 7 characters is trivial to crack … even with relatively modest hardware.
- Any password of less than 9 characters is trivial to crack if you have access to a large network of machines to work with.
- If you want to be safe for another decade or so (and policies can last quite a while), you will probably want to pick 12 characters as the minimum password length.
- These are the times to search the whole password space … it is not necessary to search through every single possible password to find the password you are looking for. That password might be found in 1/10 of the maximum time, or 3/4 of the maximum time. As long as the person generating the password has not been spectacularly dumb, it will still take a significant proportion of the total time to find the password.
If you look at the different brute force password cracking software out there, it quickly becomes apparent that there are simplistic password crackers that attempt each password combination in turn, and there are more sophisticated password crackers that attempt to tackle the most likely password combinations first. They do this by looking at passwords consisting of words, parts of words, pronounceable sequences that could be words, etc.
However good they are, all they do is increase the likelihood of obtaining the password in less than the maximum time. And possibly not by very much; let’s be generous and suppose that an intelligent brute force password cracker can produce the password on average after processing 25% of the possible passwords rather than 50% of the possible passwords. So for example for a 10 character password, an intelligent brute force password grabber could be expected to find the password after 1,500 years rather than 3,000 years (with a worst case scenario of 6,000 years in either case) … helpful, but not enough to make password cracking practical for 10 character passwords.
Poor Passwords
Everyone is obsessed with telling everyone what makes a strong password, so there’s no need for me to do likewise. But here’s my thoughts on what makes a weak password :-
- Contains a single word in any language however it may have been deformed.
- Common sequences of digits (i.e. “31415926”) or letters (“qwerty”) … they are effectively the same as words and appear in dictionaries of words to try for dictionary attacks.
- Where letters have been changed into digits is no stronger than the password with the letters would have been – the classic “monday” -> “m0nday”.
- Appending simple digits or symbols.
- Anything short; an otherwise strong password is weak if it is too short (less than 10 characters; preferably 12).
In fact the list of what makes a password weak is so long that it’s always a good idea to test how strong your password is. Preferably with a hacking tool; and not with one of those web forms where they probably don’t test too well to avoid irritating potential customers.
Passwords Suck!
Ha! Yes you’re right … passwords are now a pretty poor way of demonstrating identity. However whilst there are many alternatives, none are universal so until someone comes up with a suitable replacement we are kind of stuck with them.