Brute Force - The Attackers Last Resort

Note: This article first appeared over at our affiliates site SECOM Group. The original article can be found here.

By: Lineman

There are a number of methods that a hacker can use to guess a password such as checking defaults, checking common passwords, or using a dictionary attack. When these methods fail, there is one final guessing technique available: the brute force attack. A brute force attack, as the name implies, involves a methodical process that in theory works in any situation because every possibility is tried. The practical implementation is not guaranteed to be successful but the odds can be improved with some extra work.

The Brute Force Algorithm

The word "algorithm" tends to sound rather imposing. Creating a program that will guess every possible password might sound like quite a chore. In reality, the brute force algorithm is deceptively simple! There are several variations that can be used, but all rely on the same basic premise.

Here is one possible pattern: a,b,c,d,...,aa,ba,ca,da,...,aaa,baa,caa,...

This patter will continue through all the possible iterations until a maximum length is reached. This may look like a complex series of nested loops, but the beauty of it is, it's an algorithm you probably learned in kindergarten! Think of how you learned to write numbers. You go 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 and then add a new character and reset the original. Then you increment the second character each time the first one cycles through. Then, once all possible iterations are completed on these two characters, a third is added, and so on.

For the character pattern above, a similar process is used. The difference is, this one will add new characters to the right and will use more characters than just the ten digits (both of those differences were chosen arbitrarily and may be adapted to each individual situation). As the last possible character is chosen for a particular position, the character to the right is incremented up. When the last character needs incremented up, a new character must be added to the end.

A Sample Implementation

The following BASIC program can be used to test out the brute force attack on a password of your choosing. Try using small passwords (such as a single character) and move up to get a feel for what's happening and the time involved.

DECLARE SUB PASS.FOUND (GUESS$)
MAX.LENGTH = 8
GUESS$ = " "
LENGTH = 1
CLS
PRINT "Please enter your test password (up to 8 characters)... ";
LINE INPUT PW$
CLS
WHILE LENGTH <= MAX.LENGTH
FOR I = 32 TO 126
MID$(GUESS$, 1, 1) = CHR$(I)
PRINT GUESS$
IF GUESS$ = PW$ THEN
PASS.FOUND (GUESS$)
END IF
NEXT I
IF MID$(GUESS$, LENGTH, 1) = CHR$(126) THEN
MID$(GUESS$, LENGTH, 1) = CHR$(32)
LENGTH = LENGTH + 1
GUESS$ = GUESS$ + CHR$(32)
END IF
FOR J = 1 TO LENGTH - 1
IF MID$(GUESS$, J, 1) = CHR$(126) THEN
MID$(GUESS$, J, 1) = CHR$(32)
MID$(GUESS$, J + 1, 1) = CHR$(ASC(MID$(GUESS$, J + 1, 1)) + 1)
END IF
NEXT J
WEND
PRINT "The password was not found!"
SUB PASS.FOUND (GUESS$)
PRINT "The password is " + GUESS$ + ".";
END
END SUB

The Bottleneck

If you try the program above with passwords more than three or four characters long, you will notice a drastic increase in the time required. In that program, there are approximately 100 different characters used. That means there are approximately 100 different one-character passwords to guess, 10,000 two-character passwords to guess, and so on. Processing speed becomes a major factor very quickly!

This program would most likely be run on a computer right in front of you. Imagine trying to do the same thing over an Ethernet connection or even a dial-up! This is why a brute force attack is the last resort with password guessing as connection speed slows down the process even more.

Account Lockouts

A good administrator will fight all forms of password guessing by implementing account lockouts. In other words, after five or ten incorrect passwords, an account is locked out until the administrator unlocks it. This, at first glance, would seem to effectively eliminate password guessing.

But think about it a little more. If all accounts lock out, one could effectively lock out every user on a particular system, including the administrator! To prevent this, administrative accounts normally have locking out disabled. In other words, accounts such as admin, root, administrator, and so on can be used to avoid being locked out after only a few guesses.

Variations to Improve Efficiency

Consider guessing a four-character password using the program above. This would require 95^4 guesses (95 possible characters in 4 positions), or 81,450,625. This will take quite some time to guess.

Perhaps this can be narrowed down. Suppose that the characters used were either all capital or all lowercase letters. That narrows the guesses down to 26^4 or 456,976. Even better, if the password is made entirely of numbers like an ATM pin, then only 10^4 or 10,000 guesses are needed.

Now suppose even further that the password is a pin number that defaults to the user's birth date (even if it doesn't, many will use this anyway). This means that only 12*10^2 or 1,200 guesses are required if pin is made of a month and day.

The idea is that a little bit of research and thought can greatly improve the speed of a brute force attack. Just as adding extra characters increases the amount of time needed drastically, each little bit of information gained can be used to reduce the number of guesses drastically. A better implementation of the program above might be to check numbers first (the quickest), then all lower case, all lowercase followed by a number, and so on for each number of characters guessed.

Other Uses of the Brute Force Algorithm

There are some other possible uses for the algorithm used above. One example would be to find hidden web pages on a server. Some sites have hidden content that is not password protected but rather has an odd filename for a web page. An even more interesting place to find hidden web pages is on a router of your own, where you might find some hidden settings! A brute force attack could be used to find such pages. The number of iterations can be greatly reduced when you consider that most web pages have names of eight characters or less and that the case doesn't matter.

Another situation where the brute force algorithm could be helpful is in finding user accounts. Some servers will specify whether the password or username was wrong when guessing. Since you are only guessing one password, there is no need to worry about accounts being locked out. Once a large collection of usernames is made, a dictionary attack is more than likely to work on guessing a password to one of them.

1.) Basic Social Engineering Defense 101 - Israel
2.) How to Plan for a Possible Network Attack - Robert J. Shimonski.
3.) Brute Force - The Attackers Last Resort - Lineman
4.) X2 Free SMS Exploit - Ninja
5.) Proof Of Concept: 'Forced Analog Transmission Workaround' of the CDMA network - Ezekial
6.) Fun with Call Forwarding - Ninja