Brute force attacks from A to Z – part I

After reading and watching some very interesting views on the use of strong passwords, I must say that I don’t think we will ever be able to do without passwords. They’re here to stay. I’ll bet that the average person with an Internet connection has at least 10 passwords to remember these days. Most access methods, especially on the world wide web, rely on username-password combinations. Your web browser may take care of quite a few of them, which is a good reason why you should always update your web browser software. And even though there are some very good alternatives available, none of them are used as frequent as good-old passwords. It is widely known that you should take great care in selecting a password and change it every now and then, because you do not want a hacker to guess yours. Hackers receive quite a bit of media attention these days, and you don’t want to be on the list of their victims, right? Then you need a strong password, for starters. There are quite a few policies around on how to pick a password, each different from the other. All with the same goal: Keep your account secure. Or in general: To keep what is yours.

I find the black art of breaking passwords interesting, because it usually is a staggering amount of combination that must be tested to be successful. That is, if the password is strong enough ofcourse. If that is the case, then social engineering might be far more effective. How to attack username-passwords using a computer is very well documented and there’s a wide variety of different tools for that (hydra, john, l0phtcrack and others for example). If you were to look beyond the tools and howto’s, there are many articles about password guessing attacks that describe what they are doing and how difficult it may be for the computer to ultimately guess a password. For strong passwords, this is where the use of current day computers end because it will simply take them too long to come up with an answer. Because there is such an overwhelming amount of articles on this subject, this article will probably not add anything new, but hopefully distort your thoughts enough to think about passwords and how to create really strong ones… By trying to guess them as a computer would.

If you look at password guessing in its simplest form, it is no different than binary combinations. For example: If you were to have only two digits in a password, 0 and 1, in a password of just two digits in length; the maximum number of combinations of 0’s and 1’s in that password is 4. Being 00, 01, 10 and 11. If you replace 0 and 1 with A and B, you’ll see where this is going. Then if you were to add C to the equation, all combinations would be AA, AB, AC, BA, BB, BC, CA, CB and CC. That’s 9 in total. Basically this is 2^2 and 3^2 respectively. In general: (number of characters)^(length of password). So if you were to choose your password from only a to z, without capitals, numbers or punctuation, a 2 character password would be within 26^2 number of combinations. Here’s a small overview:

Characters used Number of characters Maximum combinations in a password of
6 characters 8 characters
[a-z] 26 308915776 208827064576
[a-z][A-Z] 52 19770609664 53459728531456
[a-z][A-Z][0-9] 62 56800235584 218340105584896
[a-z][A-Z][0-9][punct] 92 606355001344 5,13E+015
Characters used Number of characters Maximum combinations in a password of
10 characters 12 characters
[a-z] 26 141167095653376 9,54E+016
[a-z][A-Z] 52 1,45E+017 3,91E+020
[a-z][A-Z][0-9] 62 8,39E+017 3,23E+021
[a-z][A-Z][0-9][punct] 92 4,34E+019 3,68E+023

There are quite some articles around that discuss the strength of a password. Some refer to the strength of a password in terms ‘bits’, others ‘entropy‘. The C programming language defines a single character as an 8 bit integer, which would give 2^8 possibilities. That also includes control characters and other stuff that is largely inaccessible from a keyboard, so I stick to a-z ranges instead. Finding a password takes half of the amount of combinations on average. So the average number of iterations it would take to guess a 6 character password using only a to z, would be 154457888.

Well, from the table it is fairly obvious that it makes a huge difference if you add in all possible characters on your keyboard so that you have roughly 92 characters (101 if you believe most keyboard manufacturers) at your disposal, but passwords really become extremely difficult to guess when you pick a longer password.

This comic points out a common flaw of passwords: If they are “strong”, then they are often difficult to remember! And adding complexity is not always the same as adding security.

Back to the ABC password example; Suppose we’d replace A, B and C with words, instead of just characters. This is the basic setup for Diceware. Eg. A=really, B=strong, C=password, which would make a password of 20 characters and would be guessable in (26^20)/2 rounds on average. The big question here is: Is it? Would that make my password more secure? Or am I looking at a placebo that is actually stronger than 26^3 but by far nowhere near 26^20? The answer is: That depends. If you were to select the words from a list, and your password would be 3 words from that list, then the list would have to be large enough in order to make the number of combinations large. Here’s an example really short wordlist:

1 make
2 password
3 phrase
4 really
5 sentence
6 strong
7 words

The maximum number of combinations of words of a 3 word password selected from this list would only be 7^3. If an attacker knew that this was your password creation list, and knew that you were using just a few word combinations (not likely to be more than 5 or so) from it to create a password, then you’d be in trouble. On the other hand, if you were to keep this list secret, guessing a 3 word password would be quite difficult. Note that it doesn’t matter anymore if the list would contain more difficult and longer words such as:

1 {Aqu4r1um/
2 =AlUm1N1um!
3 %B4tt3r13s,
4 *Crypt0Graphy##
5 ?HeX4d3cimal^
6 )1Nf0rmaTi0n&_
7 _>InSensit1v3<;

If an attacker knew this list beforehand, a password created from it would still be guessable within 7^x rounds of computations (where x would likely be smaller than 7). But, if you did keep this list secure, a password such as “?HeX4d3cimal^{Aqu4r1um/” would be guessable in (92^24)/2 rounds! 7^5 versus 92^24 is a huge difference. A 7 word wordlist is way to short. You would need a big wordlist, only then the difficulty of guessing a password goes up:

Length of wordlist Maximum combinations
3 words 4 words 5 words
50 125000 6250000 312500000
500 125000000 62500000000 31250000000000
5000 125000000000 625000000000000 3,125e+18

When is a wordlist long enough to post it on the Internet? I wouldn’t recommend it. Even combinations of a 5 word password picked out of a 5000 word long list is no where near as strong as 24 character password picked out of 92 different characters. ((5000^5) < (92^24)) Fortunately, The Second Edition of the 20-volumeĀ Oxford English Dictionary contains full entries for 171,476 words in current use, and 47,156 obsolete words.

Epilogue

Since this is the first part of a series, there is not much of an epilogue to this article. Just one really important thing I would like to make clear:

An attacker will use every last bit of information (s)he has against you.

Knowing how you created your password makes her/his search narrower. Do not use a dictionary for your passwords. Determined hackers will very likely use one, or more. It is that simple.

There is a difference between complexity and security, especially in passwords. Creating a short complex password may be less secure than a long but simpler password.

In the next part of this series I will add in some very crude code to demonstrate what I’m getting after. Check this site every now and then…


This article is dedicated to Peter. Co-worker, roommate and one brilliant network and security architect. Your life ended way too early.

This entry was posted in IT Security and tagged , . Bookmark the permalink.